Grafo subhamiltoniano

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 ) sobre el mismo conjunto de vértices, de modo que aug( G ) sea planar y contenga un ciclo hamiltoniano . Para que esto sea cierto, G mismo debe ser planar y, además ^, debe ser posible añadir 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 denomina aumento hamiltoniano de G. [ ^{2 ]}

Sería equivalente definir G como subhamiltoniano si G es un subgrafo de un grafo planar hamiltoniano, sin requerir que este grafo mayor 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 grafo puede hacerse hamiltoniano mediante la adición de vértices y aristas, también puede hacerse hamiltoniano mediante la adición de aristas únicamente, 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 tal que al añadir una arista entre cada par consecutivo de vértices en la secuencia se conserva 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 precisamente los grafos con incrustaciones de libros de dos páginas . ^{[ 5 ]} Los grafos subhamiltonianos y las aumentaciones hamiltonianas también se han aplicado en el dibujo de grafos a problemas que involucran la incrustación de grafos en conjuntos de puntos universales , la incrustación simultánea de múltiples grafos y el dibujo de grafos en capas . ^{[ 2 ]}

Algunas clases de grafos planares son necesariamente hamiltonianos y, por lo tanto, también subhamiltonianos. Entre ellos se incluyen los grafos planares 4-conexos , según el teorema de Tutte sobre ciclos hamiltonianos ^{[ 6 ]} , y los grafos de Halin ^{[ 7 ]} .

Todo grafo planar con grado máximo como máximo cuatro es subhamiltoniano, ^{[ 4 ]} al igual que todo grafo planar sin triángulos separadores. ^{[ 8 ]} Si las aristas de un grafo planar arbitrario se subdividen en caminos de longitud dos, el grafo subdividido resultante es siempre subhamiltoniano. ^{[ 2 ]}