En el estudio matemático de la teoría de grafos , un gráfico pancíclico es un gráfico dirigido o no dirigido que contiene ciclos de todas las longitudes posibles desde tres hasta el número de vértices del gráfico. [1] Los gráficos pancíclicos son una generalización de los gráficos hamiltonianos , gráficos que tienen un ciclo de la máxima longitud posible.
Un gráfico de n -vértices G es pancíclico si, para cada en el rango, contiene un ciclo de longitud . [1] Es nodo-pancíclico o vértice-pancíclico si, para cada vértice v y cada k en el mismo rango, contiene un ciclo de longitud k que contiene v . [2] De manera similar, es borde-pancíclico si, para cada borde e y cada k en el mismo rango, contiene un ciclo de longitud k que contiene e . [2]
Un gráfico bipartito no puede ser pancíclico porque no contiene ciclos de longitud impar, pero se dice que es bipancíclico si contiene ciclos de todas las longitudes pares desde 4 hasta n . [3]
Un gráfico plano exterior máximo es un gráfico formado por un polígono simple en el plano triangulando su interior. Todo gráfico plano exterior máximo es pancíclico, como puede demostrarse por inducción. La cara exterior del gráfico es un ciclo de n vértices, y eliminando cualquier triángulo conectado al resto del gráfico por un solo borde (una hoja del árbol que forma el gráfico dual de la triangulación) se forma un gráfico plano exterior máximo en uno. menos vértices, 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 gráfico plano externo máximo es nodo-pancíclico. [4] Lo mismo se aplica a los gráficos que tienen un subgrafo que abarca el plano externo máximo , como lo hacen, por ejemplo, los gráficos de rueda .
Un gráfico plano máximo es un gráfico plano en el que todas las caras, incluso la cara exterior, son triángulos. Un gráfico plano máximo es pancíclico de nodos si y sólo 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 plano externo máximo. gráfico en los mismos nodos, a los que se puede aplicar el argumento anterior para los gráficos planos externos máximos. [6] Por ejemplo, la ilustración muestra la panciclicidad de la gráfica de un octaedro , una gráfica plana máxima hamiltoniana con seis vértices. Más claramente, según el mismo argumento, si un gráfico plano máximo tiene un ciclo de longitud k , tiene ciclos de longitudes todas más pequeñas. [7]
Los gráficos de Halin son gráficos planos formados a partir de un dibujo plano de un árbol que no tiene vértices de grado dos, agregando un ciclo al dibujo que conecta todas las hojas del árbol. Los gráficos de Halin no son necesariamente pancíclicos, pero son casi pancíclicos en el sentido de que falta como máximo una longitud de ciclo. La duración del ciclo que falta es necesariamente uniforme. Si ninguno de los vértices interiores de un gráfico 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 también eran condiciones suficientes para que un gráfico fuera pancíclico y, sobre esta base, conjeturó que todo gráfico plano de 4 conexos es pancíclico. Sin embargo, Malkevitch (1971) encontró una familia de contraejemplos.
Un torneo es un gráfico dirigido con un borde dirigido entre cada par de vértices. Intuitivamente, un torneo se puede utilizar para modelar una competición deportiva de todos contra todos , estableciendo una ventaja entre el ganador y el perdedor de cada juego de la competición. Un torneo se llama fuertemente conectado o fuerte si y sólo si no puede dividirse en dos subconjuntos no vacíos L y W de perdedores y ganadores, de manera que cada competidor en W venza a cada competidor en L. [9] Todo torneo fuerte es pancíclico [10] y nodo-pancíclico. [11] Si un torneo es regular (cada competidor tiene el mismo número de victorias y derrotas que el resto de competidores), entonces también es pancíclico; [12] sin embargo, un torneo fuerte con cuatro vértices no puede ser pancíclico.
El teorema de Mantel establece que cualquier gráfico no dirigido de n -vértices con al menos n 2/4 aristas y sin aristas múltiples ni bucles propios, contiene un triángulo o es el gráfico bipartito completo K n /2, n /2 . Este teorema se puede reforzar: cualquier gráfico hamiltoniano no dirigido con al menos n 2 /4 aristas es pancíclico o K n /2, n /2 . [1]
Existen n -gráficos dirigidos hamiltonianos de vértice con n ( n + 1)/2 - 3 aristas que no son pancíclicos, pero cada gráfico dirigido hamiltoniano con al menos n ( n + 1)/2 - 1 aristas es pancíclico. Además, cada gráfico dirigido de n vértices fuertemente conectado en el que cada vértice tiene un grado al menos n (contando los bordes entrantes y salientes juntos) es pancíclico o es un gráfico dirigido bipartito completo. [13]
Para cualquier gráfico G , su k- ésima potencia G k se define como el gráfico en el mismo conjunto de vértices que tiene un borde entre cada dos vértices cuya distancia en G es como máximo k . Si G está conectado por 2 vértices , entonces, según el teorema de Fleischner, su cuadrado G 2 es hamiltoniano; esto puede reforzarse para mostrar que es necesariamente pancíclico de vértice. [14] Más claramente, siempre que G 2 es hamiltoniano, también es pancíclico. [15]
Es NP-completo para probar si un gráfico es pancíclico, incluso para el caso especial de gráficos cúbicos de 3 conexos , y también es NP-completo para probar si un gráfico es pancíclico de nodos, incluso para el caso especial de gráficos poliédricos . [16] También es NP-completo comprobar si el cuadrado de un gráfico es hamiltoniano y, por tanto, si es pancíclico. [17]
La panciclicidad fue investigada por primera vez en el contexto de torneos por Harary y Moser (1966), Moon (1966) y Alspach (1967). El concepto de panciclicidad fue nombrado y extendido a grafos no dirigidos por Bondy (1971).
