En el estudio matemático de la teoría de grafos , un grafo pancíclico es un grafo dirigido o no dirigido que contiene ciclos de todas las longitudes posibles desde tres hasta el número de vértices del grafo. [1] Los grafos pancíclicos son una generalización de los grafos hamiltonianos , grafos que tienen un ciclo de la máxima longitud posible.
Un grafo -vértice es pancíclico si, para cada uno en el rango , contiene un ciclo de longitud . [1] Es pancíclico-nodo o pancíclico-vértice si, para cada vértice y cada uno en el mismo rango, contiene un ciclo de longitud que contiene . [2] De manera similar, es pancíclico-arista si, para cada arista y cada uno en el mismo rango, contiene un ciclo de longitud que contiene . [2]
Un gráfico bipartito no puede ser pancíclico, porque no contiene ningún ciclo de longitud impar, pero se dice que es bipancíclico si contiene ciclos de todas las longitudes pares de 4 a . [3]
Un grafo maximal exteriorplanar es un grafo formado por un polígono simple en el plano mediante la triangulación de su interior. Todo grafo maximal exteriorplanar es pancíclico, como se puede demostrar por inducción. La cara exterior del grafo es un ciclo de vértice-vértice, y al eliminar cualquier triángulo conectado al resto del grafo por una sola arista (una hoja del árbol que forma el grafo dual de la triangulación) se forma un grafo maximal exteriorplanar en un vértice menos, que por inducción tiene ciclos de todas las longitudes restantes. Con más cuidado al elegir qué triángulo eliminar, el mismo argumento muestra con más fuerza que todo grafo maximal exteriorplanar es pancíclico-nodal. [4] Lo mismo se aplica a los grafos que tienen un subgrafo de expansión exteriorplanar maximal , como por ejemplo los grafos de rueda .
Un grafo planar maximal es un grafo planar en el que todas las caras, incluso la cara exterior, son triángulos. Un grafo planar maximal es pancíclico de nodos si y solo si tiene un ciclo hamiltoniano: [5] si no es hamiltoniano, ciertamente no es pancíclico, y si es hamiltoniano, entonces el interior del ciclo hamiltoniano forma un grafo exterior planar maximal en los mismos nodos, al que se puede aplicar el argumento anterior para grafos exteriores planares maximal. [6] Por ejemplo, la ilustración muestra la panciclicidad del grafo de un octaedro , un grafo exterior planar maximal hamiltoniano con seis vértices. Más fuertemente, por el mismo argumento, si un grafo exterior planar maximal tiene un ciclo de longitud , tiene ciclos de longitudes todas menores. [7]
Los grafos de Halin son los grafos planos formados a partir de un dibujo plano de un árbol que no tiene vértices de grado dos, añadiendo un ciclo al dibujo que conecta todas las hojas del árbol. Los grafos de Halin no son necesariamente pancíclicos, pero son casi pancíclicos en el sentido de que hay como máximo una longitud de ciclo faltante. La longitud del ciclo faltante es necesariamente par. Si ninguno de los vértices interiores de un grafo de Halin tiene grado tres, entonces es necesariamente pancíclico. [8]
Bondy (1971) observó que muchas condiciones clásicas para la existencia de un ciclo hamiltoniano eran también condiciones suficientes para que un grafo fuera pancíclico y, sobre esta base, conjeturó que todo grafo plano 4-conexo es pancíclico. Sin embargo, Malkevitch (1971) encontró una familia de contraejemplos.
Un torneo es un grafo dirigido con una arista dirigida entre cada par de vértices. Intuitivamente, un torneo se puede utilizar para modelar una competición deportiva de todos contra todos , trazando una arista del ganador al perdedor de cada juego de la competición. Un torneo se llama fuertemente conectado o fuerte si y solo si no se puede dividir en dos subconjuntos no vacíos y de perdedores y ganadores, de modo que cada competidor en gane a cada competidor en . [9] Todo torneo fuerte es pancíclico [10] y pancíclico de nodos. [11] Si un torneo es regular (cada competidor tiene el mismo número de victorias y derrotas que cada otro competidor), entonces también es pancíclico de aristas; [12] sin embargo, un torneo fuerte con cuatro vértices no puede ser pancíclico de aristas.
El teorema de Mantel establece que cualquier grafo no dirigido de vértice con al menos aristas y sin aristas múltiples ni bucles propios, contiene un triángulo o es el grafo bipartito completo . Este teorema se puede reforzar: cualquier grafo hamiltoniano no dirigido con al menos aristas es pancíclico o . [1]
Existen grafos dirigidos hamiltonianos de vértice con aristas que no son pancíclicos, pero todo grafo dirigido hamiltoniano con al menos aristas es pancíclico. Además, todo grafo dirigido fuertemente conexo de vértice en el que cada vértice tiene un grado al menos (contando las aristas entrantes y salientes juntas) es pancíclico o es un grafo dirigido bipartito completo. [13]
Para cualquier grafo , su k - ésima potencia se define como el grafo en el mismo conjunto de vértices que tiene una arista entre cada dos vértices cuya distancia en es como máximo . Si es conexo por 2 vértices , entonces por el teorema de Fleischner su cuadrado es hamiltoniano; esto se puede reforzar para mostrar que es necesariamente pancíclico de vértices. [14] Más fuertemente, siempre que es hamiltoniano, también es pancíclico. [15]
Es NP-completo probar si un gráfico es pancíclico, incluso para el caso especial de gráficos cúbicos 3-conexos , y también es NP-completo probar si un gráfico es nodo-pancíclico, incluso para el caso especial de gráficos poliédricos . [16] También es NP-completo probar si el cuadrado de un gráfico es hamiltoniano y, por lo tanto, si es pancíclico. [17]
Harary y Moser (1966), Moon (1966) y Alspach (1967) investigaron por primera vez la panciclicidad en el contexto de los torneos. Bondy (1971) le dio un nombre al concepto de panciclicidad y lo extendió a los grafos no dirigidos.
