Gráfico hipohamiltoniano

En teoría de grafos , se dice que un grafo G es hipo -Hamiltoniano , si el grafo en sí no tiene un ciclo hamiltoniano , pero cualquier grafo obtenido quitando un vértice de G es hamiltoniano .

Historia

Los gráficos hipo-hamiltonianos fueron estudiados por primera vez por Sousselier en 1963 [2] . Lindgren [1] cita a Gaudin, Hertz y Rossi (1964) [3] , así como a Busaker y Saaty (1965) [4] como material adicional sobre este tema. Otro trabajo temprano es un artículo de 1967 de Hertz, Duby y Vige [5] .

Grötschel [6] resumió la mayor parte del trabajo en esta área con la siguiente declaración: "Los artículos sobre estos gráficos ... generalmente revelan nuevas clases de gráficos hipo-Hamiltonianos e hipodibujados y muestran que para algunos n tales gráficos existen, o que tienen propiedades extrañas e inesperadas".

Aplicaciones

Los gráficos hipo-hamiltonianos aparecen en soluciones enteras del problema del viajante de comercio: los gráficos hipo-hamiltonianos de cierto tipo definen facetas del poliedro del viajante de comercio , un cuerpo definido como el casco convexo del conjunto de posibles soluciones al problema del viajero de comercio, y estas facetas se pueden utilizar para métodos de plano de corte al resolver el problema con el algoritmo de Gomory [7] [6] [8] . Grötschel señaló [6] que la complejidad computacional para determinar si un gráfico es hipo-Hamiltoniano, aunque no se conoce, parece ser alta, lo que dificulta encontrar facetas de este tipo, excepto las facetas definidas por gráficos hipo-Hamiltonianos de pequeño tamaño. . Afortunadamente, los gráficos más pequeños conducen a las desigualdades más fuertes para un problema dado [9] .

Park, Lim y Kim [10] utilizaron conceptos similares a la hipo-Hamiltonianidad para medir la tolerancia a fallas de las topologías de redes de cómputo paralelo .

Propiedades

Cualquier grafo hipo-hamiltoniano debe estar conectado a 3 vértices , ya que al quitar dos vértices cualesquiera se deja un camino hamiltoniano que está conectado (un grafo al que se le quita un vértice tiene un ciclo hamiltoniano, y al quitar el segundo vértice se obtiene un camino hamiltoniano). Hay grafos hipo-hamiltonianos con n vértices, en los que el grado máximo de un vértice es n /2 y en los que hay aproximadamente n 2/4 aristas [11] .

Hertz, Duby y Vige conjeturaron [5] que cualquier gráfico hipo-hamiltoniano tiene un perímetro de 5 o más, pero la conjetura fue refutada por Thomassen [12] , quien encontró ejemplos con perímetros de 3 y 4. Durante algún tiempo no se supo si Los gráficos hipo-hamiltonianos podrían ser planos , pero ahora se conocen algunos ejemplos de tales gráficos [13] y el más pequeño de estos gráficos tiene 40 vértices [14] . Cualquier gráfico plano hipo-Hamiltoniano tiene al menos un vértice con solo tres aristas incidentes [15] .

Si es un gráfico hamiltoniano homogéneo de 3 , sus bordes se pueden colorear en tres colores: usamos alternativamente colorear los bordes con dos colores a lo largo del ciclo hamiltoniano (que debe tener una longitud uniforme según el lema del apretón de manos ), y coloreamos todos los bordes restantes con el tercer color Por lo tanto, todos los snarks , gráficos cúbicos sin puente que requieren cuatro colores para colorear los bordes, deben ser no hamiltonianos, y muchos snarks conocidos son hipo-hamiltonianos. Cualquier snark hipocamiltoniano es bicrítico : eliminar dos vértices cualesquiera deja un subgrafo cuyos bordes se pueden colorear en tres colores [16] [17] . La coloración de tres colores de este subgráfico se puede describir fácilmente: después de eliminar el vértice, la parte restante contiene un ciclo hamiltoniano. Después de eliminar el segundo vértice, el ciclo se convierte en un camino cuyos bordes se pueden colorear alternativamente con dos colores. Los bordes restantes forman una coincidencia , y todos estos bordes se pueden colorear con el tercer color.

Las clases de color de cualquier coloración de borde de 3 colores de un gráfico homogéneo de 3 forman tres coincidencias, de modo que cada borde pertenece exactamente a una coincidencia. Los snarks hipo-hamiltonianos no tienen una descomposición de emparejamiento de este tipo, pero Heggquist [18] conjeturó que los bordes de cualquier snark hipo-hamiltoniano pueden usarse para formar seis emparejamientos de modo que cada borde pertenezca exactamente a dos emparejamientos. Este es un caso especial de la conjetura de Berge-Fulkerson de que cualquier snark tiene seis coincidencias con esta propiedad.

Los gráficos hipo-hamiltonianos no pueden ser bipartitos: en un gráfico bipartito, solo se puede eliminar un vértice para formar un subgráfico hamiltoniano si pertenece a la mayor de las dos clases de color del gráfico. Sin embargo, cualquier grafo bipartito ocurre como un subgrafo generado de algún grafo hipo-Hamiltoniano [19] .

Ejemplos

El gráfico hipo-Hamiltoniano más pequeño es el gráfico de Petersen [5] . Más generalmente, un gráfico de Petersen generalizado GP( n ,2) es hipo-Hamiltoniano si n es 5 (mod 6) [20] . El gráfico de Petersen es un representante de esta construcción con n  = 5.

Lindgren [1] encontró otra clase infinita de grafos hipo-Hamiltonianos en los que el número de vértices es 4 (mod 6). La construcción de Lindgren consta de un ciclo de longitud 3 (mod 6) y un vértice central. El vértice central está conectado a cada tercer vértice del ciclo por un borde, al que llama radio, y los vértices a dos posiciones del vértice final del radio están conectados entre sí. Una vez más, el representante más pequeño de la construcción de Lindgren es el gráfico de Petersen.

Bondy [21] , Doyen y van Diest [22] y Gutt [23] dieron infinitas familias adicionales .

Enumeración

Vaclav Chvatal demostró en 1973 que para todo n suficientemente grande hay hipo-Hamiltons con n vértices. Teniendo en cuenta los descubrimientos posteriores [24] [22] , ahora se conoce "un número suficientemente grande", de modo que dichos gráficos existen para todo n ≥ 18. Se conoce una lista completa de gráficos hipo-hamiltonianos con un máximo de 17 vértices [ 25] : este es el gráfico de Petersen con 10 vértices, gráficos con 13 y 15 vértices encontrados por Hertz mediante búsqueda por computadora [26] y cuatro gráficos con 16 vértices. Hay al menos trece gráficos hipo-Hamiltonianos con 18 vértices. Aplicando el método trigger de Chvatal [27] al grafo de Petersen y al snark de la flor , se puede demostrar que el número de grafos hipo-Hamiltonianos, más específicamente, el número de snarks hipo-Hamiltonianos, crece exponencialmente con el número de vértices [28] [29] .

Generalizaciones

Los teóricos también estudian grafos hipodibujados , grafos que no contienen un camino hamiltoniano, pero en los que cualquier subconjunto de n  − 1 vértices puede estar conectado por un camino [30] [31] [32] [24] . Algunos autores han propuesto definiciones similares de hipo-Hamiltonianidad e hipodibujabilidad para grafos dirigidos [33] [34] [35] [15] .

Una definición equivalente de gráficos hipo-hamiltonianos es que sus ciclos más largos tienen una longitud n  − 1 y que la intersección de todos los ciclos más largos está vacía. Menke y Zamfirescu [36] estudiaron grafos con la propiedad de que la intersección de los ciclos más largos está vacía, pero en los que la longitud de dichos ciclos es menor que n  − 1. Hertz [26] definió la ciclabilidad de un gráfico como el número más grande k tales que cualesquiera k vértices pertenecen a un ciclo. Los gráficos hipo-hamiltonianos son exactamente gráficos que tienen una ciclicidad n  − 1. De manera similar, Park, Lim y Kim [10] definieron un gráfico como ƒ -establemente no hamiltoniano si al eliminar como máximo ƒ vértices se obtiene un subgrafo hamiltoniano. Schauerte y Zamfirescu [37] estudiaron grafos con ciclicidad n  − 2.

Notas

  1. ↑ 1 2 3 Lindgren, 1967 .
  2. ↑ Sousselier, 1963 .
  3. ↑ Gaudín, Herz, Rossi, 1964 .
  4. ↑ Busacker, Saaty, 1965 .
  5. ↑ 1 2 3 Herz, Duby, Vigué, 1967 .
  6. ↑ 1 2 3 Grötschel, 1980 .
  7. ↑ Grotschel, 1977 .
  8. ↑ Grötschel, Wakabayashi, 1981 .
  9. ↑ Goemans, 1995 .
  10. ↑ 12 Parque, Lim, Kim, 2007 .
  11. ↑ Thomassen, 1981 .
  12. ↑ Thomassen, 1974b .
  13. ↑ Václav Chvátal ( Chvátal 1973 ) planteó como pregunta abierta el problema de la existencia de grafos planares hipo-hamiltonianos y un grupo de Chvátal, Klarner y Knuth prometieron un premio de $5 al buscador de dicho gráfico ( Chvátal, Klarner , Knuth 1972 ). Thomassen ( Thomassen 1976 ) usó el teorema de Greenberg para encontrar gráficas hipo-Hamiltonianas planas con circunferencia 3, 4 y 5 y mostró que hay infinitas gráficas hipo-Hamiltonianas planas.
  14. ↑ Encontrado por Juyande, McKay, Östergaard y Pettersson ( Jooyandeh, McKay, et al. 2013 ) mediante búsqueda por computadora y el teorema de Greenberg. Antes de esto, Wiener y Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) y Zamfirescu ( Zamfirescu, Zamfirescu 2007 ) encontraron grafos planos hipo-hamiltonianos pequeños con 42, 57 y 48 vértices .
  15. ↑ 12 Thomassen , 1978 .
  16. ↑ Steffen, 1998 .
  17. ↑ Steffen, 2001 .
  18. ↑ Haggkvist, 2007 .
  19. ↑ Collier, Schmeichel, 1977 .
  20. ↑ Robertson ( 1969 ) demostró que estos gráficos no son hamiltonianos, aunque se puede verificar fácilmente que al eliminar un vértice se obtiene un gráfico hamiltoniano. Véase el artículo de Alspach ( Alspach 1983 ) sobre la clasificación de grafos de Petersen generalizados no hamiltonianos.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Consulte también la secuencia OEIS A141150 .
  26. ↑ 12 Hz , 1968 .
  27. ↑ Chavatal, 1973 .
  28. ↑ Skupień, 1989 .
  29. ↑ Skupień, 2007 .
  30. ↑ Kapoor, Kronk, Lick, 1968 .
  31. ↑ Kronk, 1969 .
  32. ↑ Grünbaum, 1974 .
  33. ↑ Fouquet, Jolivet, 1978 .
  34. ↑ Grötschel, Wakabayashi, 1980 .
  35. ↑ Grötschel, Wakabayashi, 1984 .
  36. ↑ Menke, Zamfirescu, Zamfirescu, 1998 .
  37. ↑ Schauerte, Zamfirescu, 2006 .

Literatura

Enlaces