Teorema de Fleischner

Teorema sobre grafos hamiltonianos

Un gráfico conexo de 2 vértices, su cuadrado y un ciclo hamiltoniano en el cuadrado

En teoría de grafos , una rama de las matemáticas, el teorema de Fleischner proporciona una condición suficiente para que un grafo contenga un ciclo hamiltoniano . Afirma que, si es un grafo conexo con dos vértices , entonces el cuadrado de es hamiltoniano. Recibe su nombre en honor a Herbert Fleischner , quien publicó su demostración en 1974. ${\displaystyle G}$ ${\displaystyle G}$

Definiciones y declaraciones

Un grafo no dirigido es hamiltoniano si contiene un ciclo que toca cada uno de sus vértices exactamente una vez. Es conexo por 2 vértices si no tiene un vértice de articulación, un vértice cuya eliminación dejaría al grafo restante desconectado. No todos los grafos conexos por 2 vértices son hamiltonianos; los contraejemplos incluyen el grafo de Petersen y el grafo bipartito completo . ${\displaystyle G}$ ${\displaystyle K_{2,3}}$

El cuadrado de es un grafo que tiene el mismo conjunto de vértices que , y en el que dos vértices son adyacentes si y solo si tienen una distancia de dos como máximo en . El teorema de Fleischner establece que el cuadrado de un grafo finito conexo con 2 vértices con al menos tres vértices debe ser siempre hamiltoniano. De manera equivalente, los vértices de cada grafo conexo con 2 vértices pueden organizarse en un orden cíclico tal que los vértices adyacentes en este orden estén a una distancia de dos como máximo entre sí en . ${\displaystyle G}$ ${\displaystyle G^{2}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Extensiones

En el teorema de Fleischner, es posible restringir el ciclo hamiltoniano en de modo que para los vértices dados y de incluya dos aristas incidentes con y una arista incidente con . Además, si y son adyacentes en , entonces estas son tres aristas diferentes de . ^[1] ${\displaystyle G^{2}}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$

Además de tener un ciclo hamiltoniano, el cuadrado de un grafo conexo con 2 vértices también debe ser hamiltoniano conexo (lo que significa que tiene un camino hamiltoniano que comienza y termina en dos vértices designados) y 1-hamiltoniano (lo que significa que si se elimina algún vértice, el grafo restante todavía tiene un ciclo hamiltoniano). ^[2] También debe ser pancíclico de vértices , lo que significa que para cada vértice y cada entero con , existe un ciclo de longitud que contiene . ^[3] ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle 3\leq k\leq |V(G)}$ ${\displaystyle k}$ ${\displaystyle v}$

Si un gráfico no está conexo por dos vértices, entonces su cuadrado puede tener o no un ciclo hamiltoniano, y determinar si lo tiene es NP-completo . ^[4] ${\displaystyle G}$

Un grafo infinito no puede tener un ciclo hamiltoniano, porque todo ciclo es finito, pero Carsten Thomassen demostró que si es un grafo infinito localmente finito conexo por 2 vértices y con un único extremo , entonces necesariamente tiene un camino hamiltoniano doblemente infinito. ^[5] De manera más general, si es localmente finito, conexo por 2 vértices y tiene cualquier número de extremos, entonces tiene un círculo hamiltoniano. En un espacio topológico compacto formado al ver el grafo como un complejo simplicial y agregar un punto extra en el infinito a cada uno de sus extremos, un círculo hamiltoniano se define como un subespacio que es homeomorfo a un círculo euclidiano y cubre cada vértice. ^[6] ${\displaystyle G}$ ${\displaystyle G^{2}}$ ${\displaystyle G}$ ${\displaystyle G^{2}}$

Algoritmos

El ciclo hamiltoniano en el cuadrado de un grafo 2-conexo con vértices se puede encontrar en tiempo lineal, ^[7] mejorando la primera solución algorítmica de Lau ^[8] del tiempo de ejecución . El teorema de Fleischner se puede utilizar para proporcionar una aproximación 2- al problema del viajante de comercio con cuello de botella en espacios métricos . ^[9] ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

Historia

Herbert Fleischner anunció una prueba del teorema de Fleischner en 1971 y la publicó en 1974, resolviendo una conjetura de Crispin Nash-Williams de 1966 también formulada independientemente por LW Beineke y Michael D. Plummer . ^[10] En su revisión del artículo de Fleischner, Nash-Williams escribió que había resuelto "un problema bien conocido que durante varios años ha derrotado el ingenio de otros teóricos de grafos". ^[11]

La prueba original de Fleischner era complicada. Václav Chvátal , en el trabajo en el que inventó la tenacidad de grafos , observó que el cuadrado de un grafo conexo a vértices es necesariamente tenaz; conjeturó que los grafos 2-tensos son hamiltonianos, de lo que se habría seguido otra prueba del teorema de Fleischner. ^[12] Más tarde se descubrieron contraejemplos de esta conjetura, ^[13] pero la posibilidad de que un límite finito de la tenacidad pudiera implicar hamiltonicidad sigue siendo un importante problema abierto en la teoría de grafos. Říha (1991) dio una prueba más simple tanto del teorema de Fleischner como de sus extensiones por Chartrand et al. (1974), ^[14] y Georgakopoulos (2009a) dio otra prueba simplificada del teorema. ^[15] ${\displaystyle k}$ ${\displaystyle k}$

Referencias

Notas

1. Fleischner (1976); Müttel y Rautenbach (2012).
2. Chartrand y otros (1974); Chartrand, Lesniak y Zhang (2010)
3. Hobbs (1976), respondiendo a una conjetura de Bondy (1971).
4. Subterráneo (1978); Bondy (1995).
5. Thomassen (1978).
6. Georgakopoulos (2009b); Diestel (2012).
7. Alstrup y otros (2018)
8. Lau (1980); Parker y Rardin (1984).
9. Parker y Rardin (1984); Hochbaum y Shmoys (1986).
10. Fleischner (1974). Para las conjeturas anteriores, véase Fleischner y Chartrand, Lesniak y Zhang (2010).
11. MR 0332573.
12. Chvátal (1973); Bondy (1995).
13. Bauer, Broersma y Veldman (2000).
14. Bondy (1995); Chartrand, Lesniak y Zhang (2010).
15. Chartrand, Lesniak y Zhang (2010); Diestel (2012).

Fuentes primarias

• Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva; Thomassen, Carsten (2018), "Un ciclo hamiltoniano en el cuadrado de un gráfico 2-conexo en tiempo lineal", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , págs. 1645–1649, doi : 10.1137/1.9781611975031.107 , ISBN 978-1-61197-503-1
• Bauer, D.; Broersma, HJ; Veldman, HJ (2000), "No todos los gráficos 2-tough son hamiltonianos", Actas del 5.º Taller de Twente sobre gráficos y optimización combinatoria (Enschede, 1997), Discrete Applied Mathematics , 99 (1–3): 317–321, doi : 10.1016/S0166-218X(99)00141-9 , MR  1743840.
• Bondy, JA (1971), "Gráficos pancíclicos", Actas de la Segunda Conferencia de Luisiana sobre Combinatoria, Teoría de Grafos y Computación (Louisiana State Univ., Baton Rouge, La., 1971) , Baton Rouge, Luisiana: Louisiana State University, págs. 167–172, MR  0325458.
• Chartrand, G. ; Hobbs, Arthur M. ; Jung, HA; Kapoor, SF; Nash-Williams, C. St. JA (1974), "El cuadrado de un bloque es hamiltoniano conexo", Journal of Combinatorial Theory , Serie B, 16 (3): 290–292, doi : 10.1016/0095-8956(74)90075-6 , MR  0345865.
• Chvátal, Václav (1973), "Gráficos difíciles y circuitos hamiltonianos", Matemáticas discretas , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR  0316301.
• Fleischner, Herbert (1974), "El cuadrado de cada grafo conexo es hamiltoniano", Journal of Combinatorial Theory , Serie B, 16 : 29–34, doi : 10.1016/0095-8956(74)90091-4 , MR  0332573.
• Fleischner, H. (1976), "En el cuadrado de los grafos, la hamiltonicidad y la panciclicidad, la conectividad hamiltoniana y la panconectividad son conceptos equivalentes", Monatshefte für Mathematik , 82 (2): 125–149, doi :10.1007/BF01305995, MR  0427135.
• Georgakopoulos, Agelos (2009a), "Una breve demostración del teorema de Fleischner", Discrete Mathematics , 309 (23–24): 6632–6634, doi : 10.1016/j.disc.2009.06.024 , MR  2558627.
• Georgakopoulos, Agelos (2009b), "Ciclos de Hamilton infinitos en cuadrados de grafos localmente finitos", Advances in Mathematics , 220 (3): 670–705, doi : 10.1016/j.aim.2008.09.014 , MR  2483226.
• Hobbs, Arthur M. (1976), "El cuadrado de un bloque es pancíclico de vértices", Journal of Combinatorial Theory , Serie B, 20 (1): 1–4, doi : 10.1016/0095-8956(76)90061-7 , MR  0416980.
• Hochbaum, Dorit S. ; Shmoys, David B. (1986), "Un enfoque unificado para algoritmos de aproximación para problemas de cuello de botella", Journal of the ACM , 33 (3), Nueva York, NY, EE. UU.: ACM: 533–550, doi :10.1145/5925.5933.
• Lau, HT (1980), Hallazgo de un ciclo hamiltoniano en el cuadrado de un bloque. Tesis doctoral, Montreal: McGill UniversityComo citan Hochbaum y Shmoys (1986).
• Müttel, Janina; Rautenbach, Dieter (2012), "Una breve prueba de la versión versátil del teorema de Fleischner", Matemáticas discretas , 313 (19): 1929-1933, doi : 10.1016/j.disc.2012.07.032.
• Parker, R. Garey; Rardin, Ronald L. (1984), "Heurísticas de rendimiento garantizado para el problema del viajante de comercio con cuello de botella", Operations Research Letters , 2 (6): 269–272, doi :10.1016/0167-6377(84)90077-4.
• Říha, Stanislav (1991), "Una nueva prueba del teorema de Fleischner", Journal of Combinatorial Theory , Serie B, 52 (1): 117–123, doi : 10.1016/0095-8956(91)90098-5 , MR  1109427.
• Thomassen, Carsten (1978), "Caminos hamiltonianos en cuadrados de bloques infinitos localmente finitos", en Bollobás, B. (ed.), Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, Elsevier, pp. 269–277, doi :10.1016/S0167-5060(08)70512-0, ISBN 978-0-7204-0843-0, Sr.  0499125.
• Underground, Polly (1978), "Sobre gráficos con cuadrados hamiltonianos", Matemáticas discretas , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR  0522906.

Fuentes secundarias

• Bondy, JA (1995), "Teoría básica de grafos: caminos y circuitos", Handbook of combinatorics, vol. 1, 2 , Ámsterdam: Elsevier, págs. 3-110, MR  1373656.
• Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Gráficos y dígrafos (5.ª ed.), CRC Press, pág. 139, ISBN 9781439826270.
• Diestel, Reinhard (2012), "10. Ciclos hamiltonianos", Teoría de grafos (PDF) (4.ª edición electrónica corregida)