En teoría de grafos , la conjetura de Lovász (1969) es un problema clásico sobre trayectorias hamiltonianas en grafos. Dice:
- Cada grafo transitivo de vértice conectado finito contiene un camino hamiltoniano .
Originalmente László Lovász planteó el problema de manera opuesta, pero esta versión se convirtió en estándar. En 1996, László Babai publicó una conjetura que contradecía tajantemente esta conjetura, [1] pero ambas conjeturas permanecen ampliamente abiertas. Ni siquiera se sabe si un solo contraejemplo conduciría necesariamente a una serie de contraejemplos.
Observaciones históricas
El problema de encontrar caminos hamiltonianos en gráficos altamente simétricos es bastante antiguo. Como lo describe Donald Knuth en el volumen 4 de El arte de la programación informática , [2] el problema se originó en la campanología británica (campanadas). Estos caminos y ciclos hamiltonianos también están estrechamente relacionados con los códigos Gray . En cada caso, las construcciones son explícitas.
Variantes de la conjetura de Lovász
Ciclo hamiltoniano
Otra versión de la conjetura de Lovász establece que
- Cada gráfico transitivo de vértice conectado finito contiene un ciclo hamiltoniano, excepto los cinco contraejemplos conocidos.
Hay 5 ejemplos conocidos de gráficos transitivos de vértice sin ciclos hamiltonianos (pero con caminos hamiltonianos): el gráfico completo , el gráfico de Petersen , el gráfico de Coxeter y dos gráficos derivados de los gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo. [3]
Gráficos de Cayley
Ninguno de los 5 gráficos transitivos de vértice sin ciclos hamiltonianos es un gráfico de Cayley. Esta observación conduce a una versión más débil de la conjetura:
- Cada gráfico de Cayley conectado finito contiene un ciclo hamiltoniano .
La ventaja de la formulación del gráfico de Cayley es que dichos gráficos corresponden a un grupo finito y un grupo electrógeno . Por tanto, se puede preguntar por y la conjetura se sostiene en lugar de atacarla en toda su generalidad.
Gráfico de Cayley dirigido
Para los gráficos dirigidos de Cayley (dígrafos), la conjetura de Lovász es falsa. Robert Alexander Rankin obtuvo varios contraejemplos . Aún así, muchos de los resultados a continuación se mantienen en este entorno restrictivo.
Casos especiales
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/b/b3/Steinhaus-Johnson-Trotter-Permutohedron.svg/220px-Steinhaus-Johnson-Trotter-Permutohedron.svg.png)
Cada grafo de Cayley dirigido de un grupo abeliano tiene un camino hamiltoniano; sin embargo, cada grupo cíclico cuyo orden no es una potencia primaria tiene un gráfico de Cayley dirigido que no tiene un ciclo hamiltoniano. [4] En 1986, D. Witte demostró que la conjetura de Lovász es válida para las gráficas de Cayley de grupos p . Está abierto incluso para grupos diédricos , aunque para conjuntos especiales de generadores se han realizado algunos avances.
Cuando grupo es un grupo simétrico , hay muchos grupos generadores atractivos. Por ejemplo, la conjetura de Lovász es válida en los siguientes casos de grupos electrógenos:
- (ciclo largo y transposición ).
- ( Generadores Coxeter ). En este caso, el algoritmo Steinhaus-Johnson-Trotter genera un ciclo hamiltoniano .
- cualquier conjunto de transposiciones correspondiente a un árbol etiquetado en.
Stong ha demostrado que la conjetura es válida para el gráfico de Cayley del producto de corona Z m wr Z n con el grupo electrógeno mínimo natural cuando m es par o tres. En particular, esto es válido para los ciclos conectados al cubo , que se pueden generar como el gráfico de Cayley del producto de corona Z 2 wr Z n . [5]
Grupos generales
Para grupos finitos generales, solo se conocen algunos resultados:
- ( Generadores Rankin )
- ( Generadores Rapaport – Strasser )
- ( Generadores Pak - Radoičić [6] )
- dónde (aquí tenemos (2, s, 3) - presentación , teorema de Glover-Marušič). [7]
Finalmente, se sabe que para cada grupo finito existe un grupo electrógeno de tamaño como máximo de manera que el gráfico de Cayley correspondiente es hamiltoniano (Pak-Radoičić). Este resultado se basa en la clasificación de grupos simples finitos .
La conjetura de Lovász también se estableció para conjuntos generadores aleatorios de tamaño . [8]
Referencias
- ^ Babai, László (1996), "Grupos de automorfismo, isomorfismo, reconstrucción" , Manual de combinatoria , 2 , Elsevier, págs. 1447-1540, ISBN 9780262571715
- ^ Knuth, Donald E. (2014), "§7.2.1.2 Generación de todas las permutaciones", Algoritmos combinatorios, Parte 1 , El arte de la programación informática , 4A , Addison-Wesley, ISBN 978-0-13-348885-2
- ^ Royle, Gordon, Cubic Symmetric Graphs (The Foster Census) , archivado desde el original el 20 de julio de 2008
- ^ Holsztyński, W .; Strube, RFE (1978), "Rutas y circuitos en grupos finitos", Matemáticas discretas , 22 (3): 263-272, doi : 10.1016 / 0012-365X (78) 90059-6 , MR 0522721.
- ^ Stong, Richard (1987), "Sobre los ciclos hamiltonianos en las gráficas de Cayley de productos florales", Matemáticas discretas , 65 (1): 75–80, doi : 10.1016 / 0012-365X (87) 90212-3 , MR 0891546
- ^ Pak, Igor ; Radoičić, Radoš (2009), " Rutas hamiltonianas en gráficos de Cayley" (PDF) , Matemáticas discretas , 309 (17): 5501–5508, doi : 10.1016 / j.disc.2009.02.018
- ^ Glover, Henry H .; Marušič, Dragan (2007), "Hamiltonicity of cubic Cayley graphs", Journal of the European Mathematical Society , 9 (4): 775–787, arXiv : math / 0508647 , doi : 10.4171 / JEMS / 96 , MR 2341831
- ^ Krivelevich, Michael ; Sudakov, Benny (2003), "Los gráficos pseudoaleatorios dispersos son hamiltonianos", Journal of Graph Theory , 42 : 17–33, CiteSeerX 10.1.1.24.553 , doi : 10.1002 / jgt.10065