Gráfico pancíclico

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

Definiciones

Un grafo con vértices es pancíclico si, para cualquiera dentro, el grafo contiene un ciclo de longitud [1] . Un gráfico es pancíclico de vértices si, para cualquier vértice y cualquiera dentro de los mismos límites, el gráfico contiene un ciclo de longitud que contiene el vértice [2] . De manera similar, un gráfico es pancíclico de aristas si, para cualquier arista y para cualquiera dentro de los mismos límites, contiene un ciclo de longitud que contiene la arista [2] .

Un grafo bipartito no puede ser pancíclico porque no contiene ciclos de ninguna longitud impar, pero se dice que un grafo es bipancíclico si contiene ciclos de todas las longitudes pares de 4 a [3] .

Grafos planos

Un gráfico plano exterior máximo es  un gráfico formado a partir de un polígono simple en el plano al triangularizar su interior. Cualquier gráfico de plano exterior máximo es pancíclico, lo que se puede demostrar por inducción. La cara exterior del gráfico es un ciclo con n vértices, y al eliminar cualquier triángulo conectado al resto del gráfico por solo un borde (una hoja del árbol que forma el gráfico de triangularización dual ) se forma un gráfico plano exterior máximo con un número menos de vértices, y por la suposición inductiva este gráfico tiene todos los ciclos de todas las longitudes restantes. Si se presta más atención a la elección del triángulo a eliminar, entonces los mismos argumentos muestran el resultado más riguroso de que cualquier grafo plano exterior máximo es pancíclico de vértice [4] . Lo mismo es cierto para los gráficos que tienen un gráfico plano exterior máximo como subgráfico de expansión , en particular para las ruedas .

Un gráfico plano maximal  es un gráfico plano en el que todas las caras, incluida la exterior, son triángulos. Un gráfico plano maximal es pancíclico de vértice si y solo si contiene un ciclo hamiltoniano [5]  : si no es hamiltoniano, definitivamente no es pancíclico, y si es hamiltoniano, entonces el interior del ciclo hamiltoniano forma la cara exterior. del grafo plano exterior máximo en los mismos vértices y aristas, a los que se pueden aplicar los argumentos anteriores para grafos planos exteriores [6] . Por ejemplo, en la figura[ ¿Qué? ] muestra la panciclicidad del gráfico del octaedro , un gráfico plano maximal hamiltoniano con seis vértices. Más estrictamente, por las mismas razones, si un gráfico plano maximal tiene un ciclo de longitud , tiene ciclos de todas las longitudes más pequeñas [7] .

Los gráficos de Halin son gráficos planos formados a partir de un dibujo plano de un árbol sin vértices de grado dos, añadiendo un ciclo que conecta las hojas del árbol. Los gráficos de Halin no son necesariamente pancíclicos, pero son casi pancíclicos en el sentido de que no hay un ciclo de una longitud como máximo. La duración del ciclo que falta es necesariamente uniforme. Si ninguno de los vértices internos del grafo de Halin tiene grado tres, entonces el grafo es necesariamente pancíclico [8] .

En 1971, se observó [1] que muchas condiciones clásicas para la existencia de un ciclo hamiltoniano también son suficientes para la panciclicidad y, por lo tanto, se asumió que cualquier gráfico plano conectado en 4 es pancíclico, pero pronto se encontró una familia de contraejemplos [ 9] .

Torneos

Un torneo  es un gráfico dirigido con un arco dirigido entre cualquier par de vértices. Intuitivamente, un torneo se puede usar para simular un round robin dibujando un arco desde el ganador hasta el perdedor para cada juego de la competencia. Se dice que un torneo está fuertemente conectado o simplemente fuerte si y solo si no se puede dividir en dos subconjuntos no vacíos de perdedores y ganadores, de modo que cualquier participante venza a cualquier participante en [10] . Cualquier torneo fuerte es pancíclico [11] y vértice pancíclico [12] . Si un torneo es regular (cualquier participante tiene el mismo número de victorias y derrotas que otros participantes), entonces también es pancíclico de borde [13] , pero los torneos fuertes con cuatro vértices no pueden ser pancíclicos de borde.

Gráficos con un gran número de aristas

El teorema de Mantel establece que cualquier gráficode vértice no dirigido que tenga al menosaristas y no tenga múltiples aristas o bucles contiene un triángulo o es un gráfico bipartito completo . Este teorema se puede reforzar: cualquier gráfico hamiltoniano no dirigido con al menosaristas es pancíclico o es [1] .

Hay gráficos dirigidos hamiltonianos con vértices y arcos que no son pancíclicos, pero cualquier gráfico dirigido hamiltoniano con al menos arcos es pancíclico. Además, un gráfico de vértices estrictamente conectado en el que cada vértice tiene al menos un grado (los arcos entrantes y salientes se cuentan juntos) es pancíclico o es un gráfico bipartito completo [14] .

Grados de un gráfico

Para cualquier grafo, su grado th del grafo se define como un grafo en el mismo conjunto de vértices que tiene un borde entre dos vértices cualesquiera, la distancia entre los cuales no excede . Si el vértice 2-conectado , entonces por el teorema de Fleischner es un grafo hamiltoniano. La afirmación puede reforzarse: el grafo será necesariamente pancíclico de vértice [15] . Más estrictamente, si es hamiltoniano, también es pancíclico [16] .

Complejidad computacional

Probar un gráfico para panciclicidad es un problema NP-completo incluso para el caso especial de gráficos cúbicos de 3 conexiones . También es un problema NP-completo probar la panciclicidad de un vértice en un gráfico, incluso para el caso especial de los gráficos poliédricos [17] . Además, una tarea NP-completa es probar el cuadrado de un gráfico para la hamiltonianidad y, por lo tanto, también para probar la panciclicidad [18] .

Historia

La panciclicidad fue explorada por primera vez por Harari y Moser en el contexto de los torneos [19] , así como por Muun [20] y Alpach [13] . El concepto de panciclicidad fue nombrado por Bondi, quien amplió el concepto para grafos no dirigidos [1] .

Notas

  1. ↑ 1 2 3 4 5 Bondy, 1971 .
  2. ↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
  3. ↑ Schmeichel, Mitchem, 1982 .
  4. ↑ Li, Corneil, Mendelsohn, 2000 , Proposición 2.5.
  5. ↑ Helden, 2007 , Corolario 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevitch, 1971 .
  10. ↑ Harary y Moser, 1966 , Corolario 5b.
  11. ↑ Harary y Moser, 1966 , Teorema 7.
  12. ↑ Moon, 1966 , Teorema 1.
  13. ↑ 12 Alspach , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , pág. 20–40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , Teoremas 2.3 y 2.4.
  18. ↑ Subterráneo (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Luna, 1966 .

Literatura

Enlaces