stringtranslate.com

Gráfico subhamiltoniano

En teoría de grafos y dibujo de grafos , un grafo subhamiltoniano es un subgrafo de un grafo hamiltoniano planar . [1] [2]

Definición

Un grafo G es subhamiltoniano si G es un subgrafo de otro grafo aug( G ) en el mismo conjunto de vértices, de modo que aug( G ) es plano y contiene un ciclo hamiltoniano . Para que esto sea cierto, G debe ser plano y, además, debe ser posible agregar aristas a G , preservando la planaridad, para crear un ciclo en el grafo aumentado que pase por cada vértice exactamente una vez. El grafo aug( G ) se llama aumento hamiltoniano de G . [2]

Sería equivalente definir G como subhamiltoniano si G es un subgrafo de un grafo hamiltoniano planar, sin requerir que este grafo más grande tenga el mismo conjunto de vértices. Es decir, para esta definición alternativa, debería ser posible agregar vértices y aristas a G para crear un ciclo hamiltoniano. Sin embargo, si un grafo puede volverse hamiltoniano mediante la adición de vértices y aristas, también puede volverse hamiltoniano mediante la adición de aristas solamente, por lo que esta libertad adicional no cambia la definición. [3]

En un grafo subhamiltoniano, un ciclo subhamiltoniano es una secuencia cíclica de vértices de modo que al añadir una arista entre cada par consecutivo de vértices en la secuencia se preserva la planaridad del grafo. Un grafo es subhamiltoniano si y solo si tiene un ciclo subhamiltoniano. [4]

Historia y aplicaciones

La clase de grafos subhamiltonianos (pero no este nombre para ellos) fue introducida por Bernhart y Kainen (1979), quienes demostraron que estos son exactamente los grafos con incrustaciones de libros de dos páginas . [5] Los grafos subhamiltonianos y las ampliaciones hamiltonianas también se han aplicado en el dibujo de grafos a problemas que involucran incrustaciones de grafos en conjuntos de puntos universales , incrustaciones simultáneas de múltiples grafos y dibujo de grafos en capas . [2]

Clases de gráficos relacionadas

Algunas clases de grafos planares son necesariamente hamiltonianos y, por lo tanto, también subhamiltonianos; estos incluyen los grafos planares 4-conexos [6] y los grafos de Halin . [7]

Todo grafo planar con un grado máximo de cuatro como máximo es subhamiltoniano, [4] como lo es todo grafo planar sin triángulos que lo separen. [8] Si los bordes de un grafo planar arbitrario se subdividen en caminos de longitud dos, el grafo subdividido resultante es siempre subhamiltoniano. [2]

Referencias

  1. ^ Heath, Lenwood S. (1987), "Incorporación de gráficos planos exteriores en libros pequeños", SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198–218, doi :10.1137/0608018, MR  0881181.
  2. ^ abcd Di Giacomo, Emilio; Liotta, Giuseppe (2010), "El problema de aumento hamiltoniano y sus aplicaciones al dibujo de grafos", WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, 10-12 de febrero de 2010, Actas , Lecture Notes in Computer Science, vol. 5942, Berlín: Springer, págs. 35–46, doi :10.1007/978-3-642-11440-3_4, MR  2749626.
  3. ^ Por ejemplo, en un informe técnico de 2003 "Incorporaciones de gráficos en libros y un teorema de Whitney", Paul Kainen define los gráficos subhamiltonianos como subgrafos de gráficos hamiltonianos planares, sin restricción en el conjunto de vértices de la ampliación, pero escribe que "en la definición de gráfico subhamiltoniano, se puede requerir que la extensión solo involucre la inclusión de nuevos bordes".
  4. ^ ab Bekos, Michael A.; Gronemann, Martín; Raftopoulou, Chrysanthi N. (2014), "Incrustaciones de libros de dos páginas de gráficos de 4 planos", STACS , arXiv : 1401.0684 , Bibcode : 2014arXiv1401.0684B.
  5. ^ Bernhart, Frank R.; Kainen, Paul C. (1979), "El grosor del libro de un grafo", Journal of Combinatorial Theory , Serie B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2.
  6. ^ Nishizeki, Takao ; Chiba, Norishige (2008), "Capítulo 10. Ciclos hamiltonianos", Grafos planares: teoría y algoritmos , Dover Books on Mathematics, Courier Dover Publications, págs. 171–184, ISBN 9780486466712.
  7. ^ Cornuéjols, G. ; Naddef, D.; Pulleyblank, WR (1983), "Gráficos de Halin y el problema del viajante", Programación matemática , 26 (3): 287–294, doi :10.1007/BF02591867, S2CID  26278382.
  8. ^ Kainen, Paul C.; Overbay, Shannon (2007), "Extensión de un teorema de Whitney", Applied Mathematics Letters , 20 (7): 835–837, arXiv : 2110.00820 , doi : 10.1016/j.aml.2006.08.019 , MR  2314718.