Conjetura de Lovas sobre el ciclo hamiltoniano

La conjetura de Lovas sobre el ciclo hamiltoniano es una conjetura clásica en teoría de grafos.

Fue formulado en el cuarto volumen de El arte de la programación , pero lo más probable es que se conociera mucho antes.

Redacción

Cada gráfico transitivo de vértice conexo finito contiene un camino hamiltoniano .

Variaciones y generalizaciones

Cualquier gráfico transitivo de vértice conectado finito , excepto cinco excepciones, contiene un ciclo hamiltoniano ; las excepciones son:
- gráfico completo , $K_{2}$
- El gráfico de Petersen y el gráfico obtenido a partir de él reemplazando cada vértice con un triángulo,
- El gráfico de Coxeter y el gráfico obtenido a partir de él reemplazando cada vértice por un triángulo.

gráfico completo . $K_{2}$
Conde Petersen.
Conde de Coxeter.

Ninguna de las cinco excepciones es un conde de Cayley . Esta observación conduce a una versión más débil de la hipótesis.

Cualquier gráfico de Cayley de un grupo finito contiene un ciclo hamiltoniano .

Para los gráficos de Cayley dirigidos, la conjetura no es cierta.

Casos especiales

Se sabe que un gráfico de Cayley orientado de un grupo abeliano tiene un camino hamiltoniano.
- Por otro lado, los grupos cíclicos cuyo orden no es una potencia de un primo admiten un grafo de Cayley dirigido sin ciclo hamiltoniano. [una]
En 1986, D. Witte demostró que la conjetura es cierta para las gráficas de Cayley de p-grupos .
La pregunta permanece abierta para los grupos diédricos .

Se sabe que para un grupo simétrico la conjetura es verdadera para los siguientes conjuntos de generadores:

${\ estilo de visualización a = (1,2, \ puntos, n), b = (1,2)}$ (ciclo largo y transposición ).
$s_{1}=(1,2),s_{2}=(2,3),\dots,s_{n-1}=(n-1,n)$ ( Generadores Coxeter ). En este caso, el ciclo hamiltoniano se construye mediante el algoritmo de Steinhaus-Johnson-Trotter .
$a=(1,2),b=(1,2)(3,4)\cdots,c=(2,3)(4,5)\cdots$ .

Enlaces

↑ Holsztyński, W. & Strube, RFE (1978), Rutas y circuitos en grupos finitos , Matemáticas discretas , volumen 22 (3): 263–272 , DOI 10.1016/0012-365X(78)90059-6 .