Teorema de Fleischner

El teorema de Fleischner  es una declaración en la teoría de grafos que da una condición suficiente para que un gráfico contenga un ciclo hamiltoniano : si el gráfico es un gráfico conectado por 2 vértices , entonces el cuadrado del gráfico hamiltoniano. Nombrado en honor a Herbert Fleischner , quien publicó la prueba del teorema en 1974 .

Definiciones y declaración

Un grafo no dirigido G es hamiltoniano si contiene un ciclo que pasa por cada vértice exactamente una vez. Un grafo es conectado por 2 vértices si no contiene vértices articulados, es decir, vértices cuya eliminación hace que el grafo restante sea desconectado. No todos los gráficos conectados por 2 vértices son hamiltonianos. Los contraejemplos incluyen el gráfico de Petersen y el gráfico bipartito completo K 2,3 .

Un cuadrado de un grafo G  es un grafo G 2 que tiene el mismo conjunto de vértices que el grafo G y en el que dos vértices son adyacentes si y sólo si la distancia entre ellos en G es como máximo dos. El teorema de Fleischer establece que el cuadrado de un grafo finito conectado por 2 vértices con tres o más vértices siempre debe ser hamiltoniano. De manera equivalente, los vértices de cualquier gráfico G conectado por 2 vértices se pueden organizar en un orden cíclico de modo que los vértices adyacentes en este orden en G estén separados como máximo dos entre sí.

Extensiones

En el teorema de Fleischner, se puede restringir un ciclo hamiltoniano para que incluya tres aristas elegidas que pasen por dos vértices elegidos [1] [2] .

Además de contener un ciclo hamiltoniano, el cuadrado de un grafo G conectado por 2 vértices también debe ser hamiltoniano (lo que significa que tiene un camino hamiltoniano que comienza y termina en dos vértices elegidos) y 1-Hamiltoniano (lo que significa que si elimina cualquier vértice, el gráfico restante también contendrá un ciclo hamiltoniano) [3] [4] . El gráfico también debe ser pancíclico de vértice , lo que significa que para cualquier vértice v y cualquier entero k con 3 ≤ k ≤ | V ( G )| hay un ciclo de longitud k que contiene v [5] .

Si el gráfico G no está conectado por 2 vértices, su cuadrado puede o no tener un ciclo hamiltoniano, y determinar si el gráfico tiene dicho ciclo es un problema NP-completo [6] [7] .

Un grafo infinito no puede tener un ciclo hamiltoniano, ya que cualquier ciclo es finito, pero Carsten Thomassen demostró que en el caso de que G sea un grafo infinito localmente finito con 2 vértices conectado con un solo extremo, entonces G 2 necesariamente tiene un camino hamiltoniano doblemente infinito [8] . Más generalmente, si G es localmente finito, conectado por 2 vértices y tiene cualquier número de extremos, entonces G 2 tiene un ciclo hamiltoniano. En un espacio topológico compacto , formado al tratar un gráfico como un complejo simplicial y agregar un punto extra en el infinito para cada extremo del gráfico, un ciclo hamiltoniano se define como un subespacio que es homeomorfo al círculo euclidiano y cubre todos los vértices [9 ] [10] .

Historia

La prueba del teorema fue anunciada por Herbert Fliashner en 1971 y publicada en 1974, resolviendo así la conjetura de Nash-Williams de 1966 , que también fue formulada de forma independiente por L.W. Bynik y Plummer [11] . En su revisión del artículo de Fleischner, Nash-Williams escribe que resolvió "un problema bien conocido que ha frustrado el ingenio de otros teóricos de grafos durante varios años" [12] .

La prueba original de Fleischer fue difícil. Vaclav Chvatal , en su trabajo, en el que introdujo la noción de rigidez de un gráfico , señaló que el cuadrado de un vértice -k - gráfico conexo es necesariamente k -rígido. Conjeturó que los gráficos rígidos de 2 son hamiltonianos, lo que conduciría a otra prueba del teorema de Fleischer [13] [7] . Más tarde se encontraron contraejemplos a esta conjetura [14] , pero la posibilidad de que un límite de rigidez finito pueda implicar hamiltonianidad sigue siendo un importante problema abierto en la teoría de grafos. Una prueba más simple tanto del teorema de Fleischner como de su extensión por Chartrand, Hobbs, Young y Kapuur [3] fue dada por Riha [15] [7] [4] , y otra prueba simplificada del teorema fue dada por Georgakopoulus [16] [ 4 ] ] [10] .

Notas

  1. ↑ Fleischner 1976 , pág. 125–149.
  2. ↑ Müttel, Rautenbach, 2012 .
  3. ↑ 1 2 Chartrand, Hobbs, Jung, Kapoor, 1974 .
  4. ↑ 1 2 3 Chartrand, Lesniak, Zhang, 2010 .
  5. ↑ Hobbs ( Hobbs (1976 )), respuesta a la hipótesis de Bondy ( Bondy, 1971 ).
  6. ↑ Bajo tierra, 1978 .
  7. ↑ 1 2 3 Bondy, 1995 .
  8. ↑ Thomassen (1978) .
  9. ↑ Georgakopoulos, 2009b .
  10. ↑ 12Diestel , 2012 .
  11. ↑ Fleischner (1974 ). Para hipótesis anteriores, véase Fleischner y Chartrand, Lesniak y Zhang ( Chartrand, Lesniak, Zhang (2010 )).
  12. ↑ SEÑOR : 0332573 .
  13. ↑ Chavatal, 1973 .
  14. ↑ Bauer, Broersma, Veldman, 2000 .
  15. ↑ Shiha, 1991 .
  16. ↑ Georgakopoulos, 2009a .

Literatura