Gráfico pancíclico

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 longitud máxima posible.

Un${\displaystyle n}$-grafo de vértices${\displaystyle G}$es pancíclico si, para cada${\displaystyle k}$en el rango${\displaystyle 3\leq k\leq n}$, contiene un ciclo de longitud${\displaystyle k}$. ^{[ 1 ]} Es pancíclico de nodos o pancíclico de vértices si, para cada vértice${\displaystyle v}$y cada${\displaystyle k}$en el mismo rango, contiene un ciclo de longitud${\displaystyle k}$que contiene${\displaystyle v}$. ^{[ 2 ]} De manera similar, es pancíclico de aristas si, para cada arista${\displaystyle e}$y cada${\displaystyle k}$en el mismo rango, contiene un ciclo de longitud${\displaystyle k}$que contiene${\displaystyle e}$. ^{[ 2 ]}

Un grafo 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 desde 4 hasta${\displaystyle n}$. ^{[ 3 ]}

Un grafo exteriorplanar maximal es un grafo formado por un polígono simple en el plano mediante la triangulación de su interior. Todo grafo exteriorplanar maximal es pancíclico, como se puede demostrar por inducción. La cara exterior del grafo es un${\displaystyle n}$-ciclo de vértices, y eliminando 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 exteriorplanar maximal con 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 mayor fuerza que todo grafo exteriorplanar maximal es pancíclico de nodos. ^{[ 4 ]} Lo mismo se aplica a los grafos que tienen un subgrafo generador 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 planar exterior maximal en los mismos nodos, al cual se puede aplicar el argumento anterior para grafos planares exteriores maximales. ^{[ 6 ]} Por ejemplo, la ilustración muestra la panciclicidad del grafo de un octaedro , un grafo planar maximal hamiltoniano con seis vértices. Más fuertemente, por el mismo argumento, si un grafo planar maximal tiene un ciclo de longitud${\displaystyle k}$, tiene ciclos de longitudes todas más pequeñas. ^{[ 7 ]}

Los grafos de Halin son grafos planares formados a partir de un dibujo planar de un árbol sin vértices de grado dos, añadiendo un ciclo 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 tienen 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 también eran condiciones suficientes para que un grafo fuera pancíclico, y sobre esta base conjeturó que todo grafo planar 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 puede usarse para modelar una competición deportiva de todos contra todos , trazando una arista desde el ganador hasta el perdedor de cada partido. Un torneo se denomina fuertemente conexo o fuerte si y solo si no puede dividirse en dos subconjuntos no vacíos.${\displaystyle L}$y${\displaystyle W}$de perdedores y ganadores, de tal manera que cada competidor en${\displaystyle W}$supera a todos los competidores en${\displaystyle L}$. ^{[ 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 uno de los demás competidores), 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${\displaystyle n}$-grafo no dirigido de vértices con al menos${\displaystyle n^{2}/4}$aristas, y ninguna arista múltiple o bucles propios, o bien contiene un triángulo o es el grafo bipartito completo${\displaystyle K_{n/2,n/2}}$. Este teorema puede reforzarse: cualquier grafo hamiltoniano no dirigido con al menos${\displaystyle n^{2}/4}$Los bordes son pancíclicos o${\displaystyle K_{n/2,n/2}}$. ^{[ 1 ]}

Existen${\displaystyle n}$Grafos dirigidos hamiltonianos de vértices con${\displaystyle n(n+1)/2-3}$aristas que no son pancíclicas, pero todo grafo dirigido hamiltoniano con al menos${\displaystyle n(n+1)/2-1}$Los bordes son pancíclicos. Además, cada${\displaystyle n}$-grafo dirigido fuertemente conectado de vértices en el que cada vértice tiene grado al menos${\displaystyle n}$(contando las aristas entrantes y salientes juntas) es pancíclico o es un grafo dirigido bipartito completo. ^{[ 13 ]}

Para cualquier gráfico${\displaystyle G}$, su k -ésima potencia${\displaystyle G^{k}}$se define como el grafo en el mismo conjunto de vértices que tiene una arista entre cada dos vértices cuya distancia en${\displaystyle G}$es como máximo${\displaystyle k}$. Si${\displaystyle G}$es 2-conexo-vértice , entonces por el teorema de Fleischner su cuadrado${\displaystyle G^{2}}$es hamiltoniano; esto se puede reforzar para demostrar que es necesariamente pancíclico de vértices. ^{[ 14 ]} Más fuertemente, siempre que${\displaystyle G^{2}}$es hamiltoniano, también es pancíclico. ^{[ 15 ]}

Es NP-completo comprobar si un grafo es pancíclico, incluso para el caso especial de grafos cúbicos 3-conexos , y también es NP-completo comprobar si un grafo es pancíclico en sus nodos, incluso para el caso especial de grafos poliédricos . ^{[ 16 ]} También es NP-completo comprobar si el cuadrado de un grafo es hamiltoniano y, por lo 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) .

• Panconectividad , una propiedad más fuerte en la que cada par de vértices están conectados por caminos de todas las longitudes posibles.

• Weisstein, Eric W. , "Grafo pancíclico" , MathWorld