En teoría de grafos y dibujo de grafos , un grafo subhamiltoniano es un subgrafo de un grafo hamiltoniano planar . [1] [2]
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]
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]
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]