Los grafos hipohamiltonianos fueron estudiados por primera vez por Sousselier (1963). Lindgren (1967) cita a Gaudin, Herz y Rossi (1964) y a Busacker y Saaty (1965) como trabajos iniciales adicionales sobre el tema; otro trabajo temprano es el de Herz, Duby y Vigué (1967).
Grötschel (1980) resume gran parte de la investigación en esta área con la siguiente frase: “Los artículos que tratan de esos gráficos... suelen exhibir nuevas clases de gráficos hipohamiltonianos o hipotrazables que muestran que para ciertos órdenes n tales gráficos realmente existen o que poseen propiedades extrañas e inesperadas”.
Aplicaciones
Los grafos hipohamiltonianos surgen en soluciones de programación entera al problema del viajante : ciertos tipos de grafos hipohamiltonianos definen facetas del politopo del viajante , una forma definida como la envoltura convexa del conjunto de posibles soluciones al problema del viajante, y estas facetas pueden usarse en métodos de plano de corte para resolver el problema. [1] Grötschel (1980) observa que la complejidad computacional de determinar si un grafo es hipohamiltoniano, aunque desconocida, es probable que sea alta, lo que dificulta encontrar facetas de estos tipos excepto aquellas definidas por grafos hipohamiltonianos pequeños; afortunadamente, los grafos más pequeños conducen a las desigualdades más fuertes para esta aplicación. [2]
Todo grafo hipohamiltoniano debe ser conexo por 3 vértices , ya que la eliminación de dos vértices deja un camino hamiltoniano , que es conexo. Existen grafos hipohamiltonianos de n vértices en los que el grado máximo es n /2, y en los que hay aproximadamente n 2 /4 aristas. [3]
Gráfico hipohamiltoniano de circunferencia 3 de Thomassen (1974b).
Herz, Duby y Vigué (1967) conjeturaron que todo grafo hipohamiltoniano tiene circunferencia 5 o más, pero esto fue refutado por Thomassen (1974b), quien encontró ejemplos con circunferencia 3 y 4. Durante algún tiempo se desconoció si un grafo hipohamiltoniano podía ser planar , pero ahora se conocen varios ejemplos, [4] el más pequeño de los cuales tiene 40 vértices. [5] Todo grafo hipohamiltoniano planar tiene al menos un vértice con solo tres aristas incidentes. [6]
Si un grafo 3-regular es hamiltoniano, sus aristas se pueden colorear con tres colores: use colores alternos para las aristas en el ciclo hamiltoniano (que debe tener longitud par según el lema del apretón de manos ) y un tercer color para todas las aristas restantes. Por lo tanto, todos los snarks , grafos cúbicos sin puente que requieren cuatro colores de arista, deben ser no hamiltonianos, y muchos snarks conocidos son hipohamiltonianos. Cada snark hipohamiltoniano es bicrítico : al eliminar dos vértices cualesquiera, queda un subgrafo cuyas aristas se pueden colorear con solo tres colores. [7] Una 3-coloración de este subgrafo se puede describir de manera sencilla: después de eliminar un vértice, los vértices restantes contienen un ciclo hamiltoniano. Después de eliminar un segundo vértice, este ciclo se convierte en un camino , cuyas aristas se pueden colorear alternando entre dos colores. Las aristas restantes forman una coincidencia y se pueden colorear con un tercer color.
Las clases de color de cualquier coloración de 3 colores de las aristas de un grafo 3-regular forman tres emparejamientos de modo que cada arista pertenece exactamente a uno de los emparejamientos. Los snarks hipohamiltonianos no tienen una partición en emparejamientos de este tipo, pero Häggkvist (2007) conjetura que las aristas de cualquier snark hipohamiltoniano pueden usarse para formar seis emparejamientos de modo que cada arista pertenece exactamente a dos de los emparejamientos. Este es un caso especial de la conjetura de Berge-Fulkerson de que cualquier snark tiene seis emparejamientos con esta propiedad.
Los grafos hipohamiltonianos no pueden ser bipartitos : en un grafo bipartito, un vértice solo puede eliminarse para formar un subgrafo hamiltoniano si pertenece a la mayor de las dos clases de color del grafo. Sin embargo, cada grafo bipartito ocurre como un subgrafo inducido de algún grafo hipohamiltoniano. [8]
Ejemplos
El grafo hipohamiltoniano más pequeño es el grafo de Petersen (Herz, Duby y Vigué 1967). De manera más general, el grafo de Petersen generalizado GP( n ,2) es hipohamiltoniano cuando n es congruente con 5 módulo 6; [9] el grafo de Petersen es el ejemplo de esta construcción con n = 5.
Lindgren (1967) encontró otra clase infinita de grafos hipohamiltonianos en los que el número de vértices es 4 módulo 6. La construcción de Lindgren consiste en un ciclo de longitud 3 módulo 6 y un único vértice central; el vértice central está conectado a cada tercer vértice del ciclo por aristas que él llama radios, y los vértices a dos posiciones de distancia de cada extremo de los radios están conectados entre sí. Nuevamente, el ejemplo más pequeño de la construcción de Lindgren es el grafo de Petersen.
Bondy (1972), Doyen y van Diest (1975) y Gutt (1977) dan familias infinitas adicionales.
Enumeración
Václav Chvátal demostró en 1973 que para todo n suficientemente grande existe un grafo hipohamiltoniano con n vértices. Teniendo en cuenta descubrimientos posteriores, [10] ahora se sabe que “suficientemente grande” significa que tales grafos existen para todo n ≥ 18. Se conoce una lista completa de grafos hipohamiltonianos con como máximo 17 vértices: [11] son el grafo de Petersen de 10 vértices , un grafo de 13 vértices y un grafo de 15 vértices encontrados mediante búsquedas por computadora de Herz (1968), y cuatro grafos de 16 vértices . Existen al menos trece grafos hipohamiltonianos de 18 vértices . Aplicando el método flip-flop de Chvátal (1973) al grafo de Petersen y al snark de flores , es posible demostrar que el número de grafos hipohamiltonianos, y más específicamente el número de snarks hipohamiltonianos, crece como una función exponencial del número de vértices. [12]
Generalizaciones
Los teóricos de grafos también han estudiado grafos hipotrazables , grafos que no contienen un camino hamiltoniano pero que son tales que cada subconjunto de n − 1 vértices puede estar conectado por un camino. [13] Varios autores han considerado definiciones análogas de hipohamiltonicidad e hipotrazabilidad para grafos dirigidos . [14]
Una definición equivalente de los grafos hipohamiltonianos es que su ciclo más largo tiene una longitud de n − 1 y que la intersección de todos los ciclos más largos está vacía. Menke, Zamfirescu y Zamfirescu (1998) investigan grafos con la misma propiedad de que la intersección de los ciclos más largos está vacía pero en los que la longitud del ciclo más largo es más corta que n − 1. Herz (1968) define la ciclabilidad de un grafo como el número más grande k tal que cada k vértices pertenecen a un ciclo; los grafos hipohamiltonianos son exactamente los grafos que tienen ciclabilidad n − 1. De manera similar, Park, Lim y Kim (2007) definen un grafo como hamiltoniano de ƒ-falla si la eliminación de como máximo ƒ vértices deja un subgrafo hamiltoniano. Schauerte y Zamfirescu (2006) estudian los grafos con ciclabilidad n − 2.
Notas
^ Grötschel (1977); Grötschel (1980); Grötschel y Wakabayashi (1981).
^ García (1995).
^ Thomassen (1981).
^ La existencia de grafos hipohamiltonianos planares fue planteada como una cuestión abierta por Chvátal (1973), y Chvátal, Klarner y Knuth (1972) ofrecieron un premio de 5 dólares para la construcción de uno. Thomassen (1976) utilizó el teorema de Grinberg para encontrar grafos hipohamiltonianos planares de circunferencia 3, 4 y 5 y demostró que existen infinitos grafos hipohamiltonianos planares.
^ Jooyandeh et al. (2017), utilizando una búsqueda por computadora y el teorema de Grinberg. Wiener y Araya (2009), Hatzel (1979) y Zamfirescu y Zamfirescu (2007) encontraron grafos hipohamiltonianos planos pequeños con 42, 57 y 48 vértices, respectivamente.
^ Thomassen (1978).
^ Steffen (1998); Steffen (2001).
^ Collier y Schmeichel (1977).
^ Robertson (1969) demostró que estos grafos no son hamiltonianos, mientras que es sencillo verificar que sus eliminaciones de un vértice son hamiltonianas. Véase Alspach (1983) para una clasificación de grafos de Petersen generalizados no hamiltonianos.
^ Thomassen (1974a); Decano y van Diest (1975).
^ Aldred, McKay y Wormald (1997). Véase también (secuencia A141150 en la OEIS ).
Alspach, BR (1983), "La clasificación de los grafos de Petersen generalizados hamiltonianos", Journal of Combinatorial Theory , Serie B, 34 (3): 293–312, doi : 10.1016/0095-8956(83)90042-4 , MR 0714452.
Bondy, JA (1972), "Variaciones del tema hamiltoniano", Canadian Mathematical Bulletin , 15 : 57–62, doi : 10.4153/CMB-1972-012-3.
Chvátal, V .; Klarner, DA; Knuth, DE (1972), Problemas de investigación combinatoria seleccionados (PDF) , Tech. Informe STAN-CS-72-292, Departamento de Ciencias de la Computación, Universidad de Stanford.
Collier, JB; Schmeichel, EF (1977), "Nuevas construcciones flip-flop para grafos hipohamiltonianos", Discrete Mathematics , 18 (3): 265–271, doi :10.1016/0012-365X(77)90130-3, MR 0543828.
Doyen, J.; van Diest, V. (1975), "Nuevas familias de grafos hipohamiltonianos", Discrete Mathematics , 13 (3): 225–236, doi : 10.1016/0012-365X(75)90020-5 , MR 0416979.
Fouquet, J.-L.; Jolivet, JL (1978), "Gráficos orientados hipohamiltonianos", Cahiers Centre Études Rech. Ópera. , 20 (2): 171–181, SEÑOR 0498218.
Goemans, Michel X. (1995), "Comparación del peor caso de desigualdades válidas para el TSP", Programación matemática , 69 (1–3): 335–349, CiteSeerX 10.1.1.52.8008 , doi :10.1007/BF01585563, S2CID 214113.
Grötschel, M. (1977), "Facetas hipohamiltonianas del politopo simétrico del viajante de comercio", Zeitschrift für Angewandte Mathematik und Mechanik , 58 : 469–471.
Grötschel, M. (1980), "Sobre el problema del viajante simétrico monótono: grafos y facetas hipohamiltonianos/hipotrazables", Mathematics of Operations Research , 5 (2): 285–292, doi :10.1287/moor.5.2.285, JSTOR 3689157.
Grötschel, M. ; Wakabayashi, Y. (1980), "Dígrafos hipohamiltonianos", Métodos de investigación de operaciones , 36 : 99–119, Zbl 0436.05038.
Grötschel, M. ; Wakabayashi, Y. (1981), "Sobre la estructura del politopo asimétrico monótono del viajante de comercio I: facetas hipohamiltonianas", Discrete Mathematics , 24 : 43–59, doi : 10.1016/0012-365X(81)90021-2.
Grötschel, M. ; Wakabayashi, Y. (1984), "Construcciones de dígrafos hipotrazables", en Cottle, RW; Kelmanson, ML; Korte, B. (eds.), Programación matemática (Proc. International Congress, Río de Janeiro, 1981) , Holanda Septentrional.
Grünbaum, B. (1974), "Vértices que no se detectan en los caminos o circuitos más largos", Journal of Combinatorial Theory , Serie A, 17 : 31–38, doi : 10.1016/0097-3165(74)90025-9 , MR 0349474.
Gutt, Simone (1977), "Familias infinitas de gráficos hipohamiltonianos", Académie Royale de Belgique, Bulletin de la Classe des Sciences , 5e Série, 63 (5): 432–440, SEÑOR 0498243.
Häggkvist, R. (2007), Mohar, B. ; Nowakowski, RJ; West, DB (eds.), "Problema 443. Caso especial de la conjetura de Fulkerson", Problemas de investigación de la 5.ª Conferencia eslovena (Bled, 2003), Matemáticas discretas , 307 (3–5): 650–658, doi :10.1016/j.disc.2006.07.013.
Hatzel, W. (1979), "Ein planarer hipohamiltonscher Graph mit 57 Knoten", Math. Ana. , 243 (3): 213–216, doi :10.1007/BF01424541, SEÑOR 0548801, S2CID 121794449.
Herz, JC (1968), "Sur la cyclabilité des graphes", Computers in Mathematical Research , Holanda Septentrional, págs. 97-107, MR 0245461.
Herz, JC; Duby, JJ; Vigué, F. (1967), "Recherche systématique des graphes hipohamiltoniens", en Rosenstiehl, P. (ed.), Teoría de los grafos: Simposio internacional, Roma 1966 , París: Gordon y Breach, págs. 153-159.
Jooyandeh, Mohammadreza; McKay, Brendan D .; Östergård, Patric RJ; Pettersson, Ville H.; Zamfirescu, Carol T. (2017), "Gráficos hipohamiltonianos planares en 40 vértices", Journal of Graph Theory , 84 (2): 121–133, arXiv : 1302.2698 , Bibcode :2013arXiv1302.2698J, doi :10.1002/jgt.22015.
Kapoor, SF; Kronk, HV; Lick, DR (1968), "Sobre desvíos en grafos", Canadian Mathematical Bulletin , 11 (2): 195–201, doi : 10.4153/CMB-1968-022-8 , MR 0229543.
Kronk, HV (1969), Klee, V. (ed.), "¿Existe un grafo hipotrazable?", Problemas de investigación, American Mathematical Monthly , 76 (7): 809–810, doi :10.2307/2317879, JSTOR 2317879.
Lindgren, WF (1967), "Una clase infinita de grafos hipohamiltonianos", American Mathematical Monthly , 74 (9): 1087–1089, doi :10.2307/2313617, JSTOR 2313617, MR 0224501.
Máčajová, E.; Škoviera, M. (2007), "Construcción de snarks hipohamiltonianos con conectividad cíclica 5 y 6", Electronic Journal of Combinatorics , 14 (1): R14, doi : 10.37236/936.
Menke, B.; Zamfirescu, TI; Zamfirescu, CM (1998), "Intersecciones de ciclos más largos en gráficos de cuadrícula", Journal of Graph Theory , 25 (1): 37–52, doi :10.1002/(SICI)1097-0118(199705)25:1<37::AID-JGT2>3.0.CO;2-J.
Mohanty, SP; Rao, D. (1981), "Una familia de prismas generalizados hipohamiltonianos", Combinatorics and Graph Theory , Lecture Notes in Mathematics, vol. 885, Springer-Verlag, págs. 331–338, doi :10.1007/BFb0092278, ISBN 978-3-540-11151-1.
Park, J.-H.; Lim, H.-S.; Kim, H.-C. (2007), "Panconectividad y panciclicidad de redes de interconexión de tipo hipercubo con elementos defectuosos", Theoretical Computer Science , 377 (1–3): 170–180, doi :10.1016/j.tcs.2007.02.029.
Robertson, GN (1969), Gráficos mínimos bajo restricciones de circunferencia, valencia y conectividad , tesis doctoral, Waterloo, Ontario: Universidad de Waterloo.
Schauerte, Boris; Zamfirescu, CT (2006), "Gráficos regulares en los que cada par de puntos se pierde en algún ciclo más largo", An. Univ. Craiova Ser. Mat. Inform. , 33 : 154–173, hdl : 1854/LU-6901462 , MR 2359901.
Skupień, Z. (1989), "Exponencialmente muchos grafos hipohamiltonianos", Graphs, Hypergraphs and Matroids III (Proc. Conf. Kalsk 1988) , Zielona Góra: Higher College of Engineering, págs. 123–132. Como lo cita Skupień (2007).
Skupień, Z. (2007), "Muchos snarks hipohamiltonianos exponencialmente", 6.º Simposio internacional checo-eslovaco sobre combinatoria, teoría de grafos, algoritmos y aplicaciones , Electronic Notes in Discrete Mathematics, vol. 28, págs. 417–424, doi :10.1016/j.endm.2007.01.059.
Sousselier, R. (1963), Berge, C. (ed.), "Problème no. 29: Le cercle des irascibles", Problèmes plaisants et délectables, Rev. Franç. Rech. Opérationnelle , 7 : 405–406.
Steffen, E. (1998), "Clasificación y caracterización de snarks", Discrete Mathematics , 188 (1–3): 183–203, doi : 10.1016/S0012-365X(97)00255-0 , MR 1630478.
Steffen, E. (2001), "Sobre los sarcasmos bicríticos", Math. Slovaca , 51 (2): 141–150, MR 1841443.
Thomassen, Carsten (1974a), "Gráficos hipohamiltonianos e hipotrazables", Discrete Mathematics , 9 : 91–96, doi :10.1016/0012-365X(74)90074-0, MR 0347682.
Zamfirescu, CT; Zamfirescu, TI (2007), "Un gráfico hipohamiltoniano planar con 48 vértices", Journal of Graph Theory , 55 (4): 338–342, doi :10.1002/jgt.20241.
