Si un gráfico de $2n$ vértices contiene un ciclo hamiltoniano, entonces podemos llegar a cualquier otro vértice en $n$ ¿pasos?

Question

El problema: Dado un gráfico $G,$ con $2n$ vértices y al menos un triángulo. ¿Es posible demostrar que se puede alcanzar cualquier otro vértice en $n$ pasos si $G$ contiene un ciclo de Hamilton (HC)?

EDITAR : Lo siento, me olvidé de mencionar, que $G$ es planar y de 3 conexiones. Una prueba completa para $3$ -los gráficos regulares también serían aceptados/recompensados.

¿Funciona lo siguiente como prueba?

Elija un vértice inicial $v_0$ y una dirección.

• Si caminas por la HC llegarás a un vértice $v_{n-1}$ con la máxima distancia de $v_0$ en $n$ pasos.
• Llegarás a $v_{n-2}$ haciendo una ronda en el triángulo y
• $v_{n-3}$ retrocediendo en el último paso.
• Combinando estos movimientos, alcanzarás la mitad de todos los $v_k$ .
• Si eliges la otra dirección al principio, llegarás a la otra mitad.
• $v_0$ es libre de elegir.

Demostrar o refutar la "sólo si" ¡-parte también estaría bien!

Answer 1

Sólo si: Tener un triángulo y poder viajar entre dos vértices cualesquiera en exactamente $n$ pasos no implica un ciclo hamiltoniano. Consideremos el Gráfico de la piruleta $L_{5,1}$ Si se puede llegar a dos puntos cualesquiera en exactamente tres pasos, obviamente contiene un triángulo y no contiene un camino hamiltoniano. Para ver que cada par de puntos distintos se puede alcanzar en tres pasos, consideremos primero dos vértices en el $K_5$ hay un camino de longitud 3 que se hace visitando dos de los vértices del $K_5$ diferentes de los vértices inicial y final. A continuación, considere el camino desde el vértice de grado 1 a un vértice en el $K_5$ , ir al vértice de grado 6, luego visitar un vértice de la $K_5$ que no sea el vértice de grado 6 o el vértice final, y luego terminar.

Tampoco me gusta tu prueba de la dirección "si". Considera un ciclo de longitud 7 con un triángulo adyacente. No se puede viajar desde el punto opuesto al triángulo a un punto adyacente a él en 4 pasos. Esto puede ser más sencillo de visualizar como un ciclo de longitud 8 con dos vértices distanciados dos unidos. La razón por la que tu prueba falla es que el triángulo está demasiado lejos para ser útil.

En la imagen adjunta, no se puede viajar desde $a$ a $b$ en exactamente cuatro pasos.

Answer 2

Es el problema de alcanzar cualquier otro vértice desde un punto de partida dado $v_0$ en $n$ ¿pasos? Si es así, ¿por qué no ignorar el triángulo? El camino tiene una longitud $2n$ , por lo que el punto más lejano es $n$ a lo largo del camino.

Añadido para la parte no sólo si: Ver abajo. Se puede llegar a cualquier parte en tres pasos de $v_1$ pero no de $v_4$ . No me quedó claro si hay que llegar a algún sitio desde un lugar en $n$ pasos o en cualquier lugar de cualquier $n$ pasos.

Answer 3

La respuesta es no .

Pregunta: Dejemos que $G$ sea un grafo planar hamiltoniano de 3 conexiones con $2n$ vértices y al menos un triángulo. ¿Es cierto que para todos los pares de vértices $x,y$ que hay un paseo de exactamente $n$ pasos de $x$ a $y$ ?

El siguiente gráfico y par de vértices es un contraejemplo

Está claro que la gráfica es plana y tiene un triángulo. Se puede comprobar fácilmente que el gráfico está conectado por 3. Para mostrar que el gráfico es hamiltoniano, he resaltado un ciclo hamiltoniano aquí

Como el vértice tiene 16 vértices, necesitamos verificar que no hay ningún paseo de longitud 8 desde $x$ a $y$ . Desde $n$ es igual, no podemos alcanzar $y$ sin utilizar algunos de los cuatro vértices de la derecha. Ahora es fácil verificar a mano, que no hay ningún paseo de $x$ a $y$ de longitud exactamente 8.