Panconectividad

En teoría de grafos , un grafo panconexo es un grafo no dirigido en el que, para cada par de vértices s y t , existen caminos de s a t de cualquier longitud posible desde la distancia d ( s , t ) hasta n − 1 , donde n es el número de vértices del grafo. El concepto de panconectividad fue introducido en 1975 por Yousef Alavi y James E. Williamson. ^{[ 1 ]}

Los grafos panconexos son necesariamente pancíclicos : si uv es una arista , pertenece a un ciclo de cualquier longitud posible y, por lo tanto, el grafo contiene un ciclo de cualquier longitud posible. Los grafos panconexos también son una generalización de los grafos hamiltonianos conexos (grafos que tienen un camino hamiltoniano que conecta cada par de vértices).

Se sabe que varias clases de grafos son panconexos:

• Si G tiene un ciclo hamiltoniano , entonces el cuadrado de G (el grafo sobre el mismo conjunto de vértices que tiene una arista entre cada par de vértices cuya distancia en G es como máximo dos) es panconexo. ^{[ 1 ]}
• Si G es cualquier grafo conexo , entonces el cubo de G (el grafo sobre el mismo conjunto de vértices que tiene una arista entre cada par de vértices cuya distancia en G es como máximo tres) es panconexo. ^{[ 1 ]}
• Si cada vértice en un grafo de n vértices tiene un grado de al menos n /2 + 1 , entonces el grafo es panconexo. ^{[ 2 ]}
• Si un grafo de n vértices tiene al menos ( n − 1)( n − 2)/2 + 3 aristas, entonces el grafo es panconexo. ^{[ 2 ]}

Grafos pancíclicos de vértices : Un grafo de orden n es pancíclico de vértices si cada vértice se encuentra en ciclos de cualquier longitud posible desde la circunferencia del grafo hasta n . Si bien los grafos pancíclicos de vértices no necesariamente son panconexos, comparten la propiedad de tener estructuras de ciclos ricas. ^{[ 3 ]}

Grafos hamiltonianos conexos : Son grafos donde cada par de vértices está conectado por un camino hamiltoniano . Todos los grafos panconexos son hamiltonianos conexos, pero lo contrario no es cierto. Por ejemplo, los grafos L ( n ) ( grafos de líneas de ciertos grafos de inclusión ) son hamiltonianos conexos para n ≥ 4 , pero no panconexos. ^{[ 3 ]}