En el estudio matemático de la teoría de grafos , un grafo pancíclico es un grafo dirigido o un grafo no dirigido que contiene ciclos de todas las longitudes posibles desde tres hasta el número de vértices en el 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.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/77/Pancyclic_octahedron.svg/220px-Pancyclic_octahedron.svg.png)
Definiciones
Un gráfico de n -vértices G es pancíclico si, para cada en el rango contiene un ciclo de duración . [1] Es nodo-pancíclico o vértice-pancíclico si, para cada vértice vy 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 grafo bipartito no puede ser pancyclic, porque no contiene ningún ciclos de longitud impar, pero se dice que es bipancyclic si contiene ciclos de todas las longitudes incluso de 4 a n . [3]
Gráficos planos
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 externo máximo es pancíclico, como se puede demostrar por inducción. La cara exterior del gráfico es un ciclo de n- vértices, y eliminar 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) forma un gráfico plano exterior máximo en uno. menos vértice, 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 cada grafo del plano exterior máximo es de nódulos pancíclicos. [4] Lo mismo se aplica a los gráficos que tienen un subgráfico de extensión del plano exterior máximo , como ocurre, por ejemplo, con 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 grafo plano máximo es nódulo-pancíclico 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 plano externo máximo gráfico en los mismos nodos, a los que se puede aplicar el argumento anterior para 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 fuertemente, por el mismo argumento, si un gráfico plano máximo tiene un ciclo de longitud k , tiene ciclos de todas las longitudes más pequeñas. [7]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/f/f6/Halin_no_8-cycle.svg/220px-Halin_no_8-cycle.svg.png)
Los gráficos de Halin son los 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 duración de ciclo. La duración del ciclo faltante 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 eran también condiciones suficientes para que un gráfico fuera pancíclico, y sobre esta base conjeturó que todo gráfico plano de 4 conexiones es pancíclico. Sin embargo, Malkevitch (1971) encontró una familia de contraejemplos.
Torneos
Un torneo es un gráfico dirigido con un borde dirigido entre cada par de vértices. De manera intuitiva, un torneo se puede utilizar para modelar una competencia deportiva de todos contra todos , sacando una ventaja del ganador al perdedor de cada juego en la competencia. Un torneo se llama fuertemente conectada o fuerte si y sólo si no se puede dividir en dos subconjuntos no vacíos L y W de perdedores y ganadores, de tal manera que cada competidor en W late cada competidor en L . [9] Todo torneo fuerte es pancíclico [10] y nódulo-pancíclico. [11] Si un torneo es regular (cada competidor tiene el mismo número de victorias y derrotas que los demás), entonces también es pancíclico de borde; [12] sin embargo, un torneo fuerte con cuatro vértices no puede ser pancíclico de borde.
Gráficos con muchas aristas
Teorema de Mantel estados que cualquier n -vertex grafo no dirigido con al menos n 2 /4 bordes, y no hay bordes múltiples o auto-bucles, o bien contiene un triángulo o es el grafo bipartito completo K n / 2, n / 2 . Este teorema puede fortalecerse: cualquier gráfico hamiltoniano no dirigido con al menos n 2 /4 bordes es o bien pancyclic o K n / 2, n / 2 . [1]
Existen grafos dirigidos hamiltonianos de n -vértices con n ( n + 1) / 2 - 3 aristas que no son pancíclicas, pero cada grafo dirigido hamiltoniano con al menos n ( n + 1) / 2 - 1 aristas es pancíclico. Además, cada gráfico dirigido fuertemente conectado de n -vértices 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]
Potencias gráficas
Para cualquier gráfica G , su k- ésima potencia G k se define como la gráfica en el mismo conjunto de vértices que tiene una arista 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 fuertemente, siempre que G 2 es hamiltoniano, también es pancíclico. [15]
Complejidad computacional
Es NP-complete para probar si una gráfica es pancíclica, incluso para el caso especial de gráficas cúbicas conectadas a 3 , y también es NP-complete para probar si una gráfica es de nodo-pancíclico, incluso para el caso especial de gráficas poliédricas. . [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]
Historia
La panciclicidad fue investigada por primera vez en el contexto de los torneos por Harary y Moser (1966) , Moon (1966) y Alspach (1967) . Bondy (1971) nombró el concepto de panciclicidad y lo amplió a gráficos no dirigidos .
Notas
- ↑ a b c Bondy (1971) .
- ^ a b Randerath y col. (2002) .
- ^ Schmeichel y Mitchem (1982) .
- ^ Li, Corneil y Mendelsohn (2000) , Proposición 2.5.
- ^ Helden (2007) , Corolario 3.78.
- ^ Bernhart y Kainen (1979) .
- ^ Hakimi y Schmeichel (1979) .
- ^ Skowrońska (1985) .
- ^ Harary y Moser (1966) , Corolario 5b.
- ^ Harary y Moser (1966) , Teorema 7.
- ^ Luna (1966) , Teorema 1.
- ^ Alspach (1967) .
- ^ Häggkvist y Thomassen (1976) .
- ^ Hobbs (1976) .
- ^ Fleischner (1976) .
- ^ Li, Corneil y Mendelsohn (2000) , Teoremas 2.3 y 2.4.
- ^ Subterráneo (1978) .
Referencias
- Alspach, Brian (1967), "Ciclos de cada duración en torneos regulares" , Canadian Mathematical Bulletin , 10 (2): 283–286, doi : 10.4153 / cmb-1967-028-6.
- Bernhart, Frank; Kainen, Paul C. (1979), "El grosor del libro de un gráfico", Journal of Combinatorial Theory , Serie B , 27 (3): 320–331, doi : 10.1016 / 0095-8956 (79) 90021-2.
- Bondy, JA (1971), "Gráficos pancíclicos I", Journal of Combinatorial Theory , Serie B , 11 (1): 80-84, doi : 10.1016 / 0095-8956 (71) 90016-5.
- Fleischner, H. (1976), "En el cuadrado de los gráficos, hamiltonicidad y panciclicidad, conectividad hamiltoniana y panconexión son conceptos equivalentes", Monatshefte für Mathematik , 82 (2): 125-149, doi : 10.1007 / BF01305995 , MR 0427135.
- Häggkvist, Roland; Thomassen, Carsten (1976), "Sobre dígrafos pancíclicos", Journal of Combinatorial Theory , Serie B , 20 (1): 20–40, doi : 10.1016 / 0095-8956 (76) 90063-0.
- Hakimi, SL ; Schmeichel, EF (1979), "Sobre el número de ciclos de longitud k en un gráfico plano máximo", Journal of Graph Theory , 3 : 69–86, doi : 10.1002 / jgt.3190030108.
- Harary, Frank ; Moser, Leo (1966), "La teoría de los torneos round robin", American Mathematical Monthly , 73 (3): 231–246, doi : 10.2307 / 2315334.
- Helden, Guido (2007), Hamiltonicity of maximal planar graphs and planar triangulations (PDF) , Disertación, Rheinisch-Westfälischen Technischen Hochschule Aachen, archivado desde el original (PDF) en 2011-07-18.
- Hobbs, Arthur M. (1976), "El cuadrado de un bloque es el vértice pancíclico", Journal of Combinatorial Theory , Serie B, 20 (1): 1-4, doi : 10.1016 / 0095-8956 (76) 90061-7 , MR 0416980.
- Li, Ming-Chu; Corneil, Derek G .; Mendelsohn, Eric (2000), "Panciclicidad y completitud NP en gráficas planas", Matemáticas aplicadas discretas , 98 (3): 219-225, doi : 10.1016 / S0166-218X (99) 00163-8.
- Malkevitch, Joseph (1971), "Sobre la duración de los ciclos en gráficas planas", Tendencias recientes en la teoría de grafos , Lecture Notes in Mathematics, 186 , Springer-Verlag, págs. 191-195, doi : 10.1007 / BFb0059437.
- Moon, JW (1966), "Sobre los sub-torneos de un torneo" , Canadian Mathematical Bulletin , 9 (3): 297–301, doi : 10.4153 / CMB-1966-038-7.
- Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike; Volkmann, Lutz (2002), "Gráficos pancíclicos de vértice", Matemáticas aplicadas discretas , 120 (1–3): 219–237, doi : 10.1016 / S0166-218X (01) 00292-X.
- Schmeichel, Edward; Mitchem, John (1982), "Gráficos bipartitos con ciclos de todas las longitudes pares", Journal of Graph Theory , 6 (4): 429–439, doi : 10.1002 / jgt.3190060407.
- Skowrońska, Mirosława (1985), "La panciclicidad de los gráficos de Halin y sus contracciones exteriores", en Alspach, Brian R .; Godsil, Christopher D. (eds.), Cycles in Graphs , Annals of Discrete Mathematics, 27 , Elsevier Science Publishers BV, págs. 179–194.
- Underground, Polly (1978), "Sobre gráficas con cuadrados hamiltonianos", Matemáticas discretas , 21 (3): 323, doi : 10.1016 / 0012-365X (78) 90164-4 , MR 0522906.
enlaces externos
- Weisstein, Eric W. "Gráfico pancíclico" . MathWorld .