En teoría de grafos y dibujo de grafos , un grafo subhamiltoniano es un subgrafo de un grafo planar hamiltoniano . [1] [2]
Definición
Un gráfico G es subhamiltoniano si G es un subgráfico de otro gráfico 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 , conservando la planaridad, para crear un ciclo en el gráfico aumentado que pase por cada vértice exactamente una vez. AUG gráfico ( G ) se llama un aumento hamiltoniano de G . [2]
Sería equivalente definir G como subhamiltoniano si G es un subgrafo de un gráfico plano hamiltoniano, sin requerir que este gráfico más grande tenga el mismo conjunto de vértices. Es decir, para esta definición alternativa, debería ser posible agregar tanto vértices como aristas a G para crear un ciclo hamiltoniano. Sin embargo, si un gráfico se puede hacer hamiltoniano mediante la adición de vértices y aristas, también se puede hacer hamiltoniano solo con la adición de aristas, por lo que esta libertad adicional no cambia la definición. [3]
En un gráfico subhamiltoniano, un ciclo subhamiltoniano es una secuencia cíclica de vértices de modo que agregar un borde entre cada par consecutivo de vértices en la secuencia conserva la planaridad del gráfico. Una gráfica es subhamiltoniana si y solo si tiene un ciclo subhamiltoniano. [4]
Historia y aplicaciones
Bernhart y Kainen (1979) introdujeron la clase de gráficos subhamiltonianos (pero no este nombre ) , quienes demostraron que estos son exactamente los gráficos con incrustaciones de libros de dos páginas . [5] Los gráficos subhamiltonianos y los aumentos hamiltonianos también se han aplicado en el dibujo de gráficos a problemas que involucran la incrustación de gráficos en conjuntos de puntos universales , la incrustación simultánea de múltiples gráficos y el dibujo de gráficos en capas . [2]
Clases de grafos relacionados
Algunas clases de grafos planos son necesariamente hamiltonianos y, por tanto, también subhamiltonianos; estos incluyen los gráficos planos de 4 conectados [6] y los gráficos de Halin . [7]
Todo gráfico plano con un grado máximo como máximo cuatro es subhamiltoniano, [4] al igual que todo gráfico plano sin triángulos de separación. [8] Si los bordes de un gráfico plano arbitrario se subdividen en trayectos de longitud dos, el gráfico subdividido resultante es siempre subhamiltoniano. [2]
Referencias
- ^ Heath, Lenwood S. (1987), "Incrustar gráficos de planos externos en libros pequeños", SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198-218, doi : 10.1137 / 0608018 , MR 0881181.
- ^ a b c d Di Giacomo, Emilio; Liotta, Giuseppe (2010), "The Hamiltonian augmentation problem and its applications to graph drawing", WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, 10-12 de febrero de 2010, Proceedings , Lecture Notes in Computer Science, 5942 , Berlín: Springer, págs. 35–46, doi : 10.1007 / 978-3-642-11440-3_4 , MR 2749626.
- ^ Por ejemplo, en un informe técnico de 2003 " Libro incrustaciones de gráficos y un teorema de Whitney ", Paul Kainen define los gráficos subhamiltonianos como subgráficos de gráficos planos hamiltonianos, sin restricción en el conjunto de vértices del aumento, pero escribe que "en la definición del grafo subhamiltoniano, se puede requerir que la extensión solo implique la inclusión de nuevos bordes ".
- ^ a b Bekos, Michael A .; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), " Embeddings de libros de dos páginas de gráficos de 4 planos", STACS , arXiv : 1401.0684 , Bibcode : 2014arXiv1401.0684B.
- ^ Bernhart, Frank R .; Kainen, Paul C. (1979), "El grosor del libro de un gráfico", Journal of Combinatorial Theory , Serie B, 27 (3): 320–331, doi : 10.1016 / 0095-8956 (79) 90021-2.
- ^ Nishizeki, Takao ; Chiba, Norishige (2008), "Capítulo 10. Ciclos hamiltonianos", Gráficos planos: teoría y algoritmos , Dover Books on Mathematics, Courier Dover Publications, pp. 171-184, ISBN 9780486466712.
- ^ 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.
- ^ Kainen, Paul C .; Overbay, Shannon (2007), "Extensión de un teorema de Whitney", Letras de matemáticas aplicadas , 20 (7): 835–837, doi : 10.1016 / j.aml.2006.08.019 , MR 2314718.