Número de cruce de K (9, 9)

Question

Estoy estudiando teoría de grafos y no sé cómo resolver este problema. No soy muy bueno con los gráficos y me resulta bastante difícil resolver este tipo de problemas. Le agradecería mucho si me pudiera dar alguna explicación. ¡Gracias por adelantado!

Pregunta: ¿Es cierto que cada k-conectado ($k>1$) gráfico que no tiene un ciclo hamiltoniano tiene un ciclo que contiene $k$vértices independientes y sus vecinos? Se sabe que esto es cierto para$k = 2$ y $3$. Por ejemplo, la gráfica de la derecha tiene 3 conexiones pero no es hamiltoniana. Y el ciclo de puntos que se muestra contiene$3$vértices independientes (los tres vértices que son de color más claro) y sus vecinos. Para ver que no es hamiltoniano, observe que este gráfico es solo el gráfico bipartito completo$K(3,4)$.

Answer 1

Primero pensemos en el caso cuando $G$está conectado. Si$|V| < k$, entonces ciertamente no podemos particionar $V$ dentro $k$ subconjuntos no vacíos, así que supongamos $|V| \geq k$.

Afirmo que en este caso hay una partición adecuada. Para mostrar esto, basta con encontrar un subconjunto$V' \subseteq V$ con $|V'| = k-1$ tal que $G - V'$ está conectado: entonces podemos tomar $V_1$ ser - estar $V - V'$ y podemos $V'$ en conjuntos con un elemento cada uno para obtener $V_2,\dots,V_k$. ¿Cómo encontramos tal$V'$? Intuitivamente, tomamos un árbol de expansión$G$ y "arranca" las hojas una por una hasta que hayamos roto $k-1$. Formalmente, podemos atravesar$G$según algún algoritmo (por ejemplo, DFS). Dejar$v_1, \dots, v_n$será el orden en el que visitamos los vértices durante este recorrido. El hecho de que podamos atravesar los vértices en este orden muestra que la primera$n-(k-1)$ vértices inducen un subgrafo conectado de $G$, entonces podemos tomar $V'$ ser el ultimo $k-1$ vértices.

Y si $G$no esta conectado? Bueno, si tiene más componentes conectados que$k$, entonces no puede haber tal partición (¿por qué?). De lo contrario (siempre que$|V| \geq k$) podemos utilizar esencialmente la misma idea: tomar un bosque de expansión $G$ y desprenda las hojas hasta que el número de hojas arrancadas más el número de los componentes conectados restantes sea $k$. Nuevamente, esto se puede hacer usando un orden transversal, solo que en este caso es necesario pensar un poco para determinar cuántas hojas debemos cortar.