Gráfico de Petersen

En el campo matemático de la teoría de grafos , el grafo de Petersen es un grafo no dirigido con 10 vértices y 15 aristas . Es un grafo pequeño que sirve como ejemplo y contraejemplo útil para muchos problemas en teoría de grafos. El grafo de Petersen recibe su nombre de Julius Petersen , quien en 1898 lo construyó para que fuera el grafo cúbico sin puentes más pequeño sin coloración de tres aristas . ^{[ 1 ] [ 2 ]}

Aunque generalmente se atribuye el gráfico a Petersen, en realidad apareció por primera vez 12 años antes, en un artículo de AB Kempe ( 1886 ) . Kempe observó que sus vértices pueden representar las diez líneas de la configuración de Desargues , y sus aristas representan pares de líneas que no se encuentran en ninguno de los diez puntos de la configuración. ^{[ 3 ]} 

Donald Knuth afirma que el grafo de Petersen es "una configuración notable que sirve como contraejemplo a muchas predicciones optimistas sobre lo que podría ser cierto para los grafos en general". ^{[ 4 ]}

El gráfico de Petersen también aparece en la geometría tropical . El cono sobre el gráfico de Petersen se identifica naturalmente con el espacio de módulos de curvas tropicales racionales de cinco puntas. ^{[ 5 ]}

El grafo de Petersen es el complemento del grafo de líneas de K ₅ . También es el grafo de Kneser KG _5,2 ; esto significa que tiene un vértice por cada subconjunto de 2 elementos de un conjunto de 5 elementos, y dos vértices están conectados por una arista si y solo si los subconjuntos de 2 elementos correspondientes son disjuntos entre sí. Como grafo de Kneser de la forma KG _{2 n −1, n −1} es un ejemplo de un grafo impar .

Geométricamente, el grafo de Petersen es el grafo formado por los vértices y las aristas del hemidodecaedro , es decir, un dodecaedro con puntos, líneas y caras opuestas identificadas entre sí.

El grafo de Petersen no es planar . Cualquier grafo no planar tiene como menores el grafo completo K ₅ o el grafo bipartito completo K _3,3 , pero el grafo de Petersen tiene ambos como menores. El menor K ₅ se puede formar contrayendo las aristas de un emparejamiento perfecto , por ejemplo, las cinco aristas cortas de la primera imagen. El menor K _3,3 se puede formar eliminando un vértice (por ejemplo, el vértice central del dibujo 3-simétrico) y contrayendo una arista incidente a cada vecino del vértice eliminado.

El dibujo plano más común y simétrico del grafo de Petersen, como un pentagrama dentro de un pentágono, tiene cinco cruces. Sin embargo, este no es el mejor dibujo para minimizar los cruces; existe otro dibujo (mostrado en la figura) con solo dos cruces. Debido a que no es planar, tiene al menos un cruce en cualquier dibujo, y si se elimina una arista de cruce de cualquier dibujo, sigue siendo no planar y tiene otro cruce; por lo tanto, su número de cruces es exactamente 2. Cada arista en este dibujo se cruza como máximo una vez, por lo que el grafo de Petersen es 1-planar . En un toro, el grafo de Petersen se puede dibujar sin cruces de aristas; por lo tanto, tiene género orientable 1.

El grafo de Petersen también se puede dibujar (con cruces) en el plano de tal manera que todas las aristas tengan la misma longitud. Es decir, es un grafo de distancia unitaria .

La superficie no orientable más simple sobre la que se puede incrustar el grafo de Petersen sin cruces es el plano proyectivo . Esta es la incrustación que proporciona la construcción del hemidodecaedro del grafo de Petersen (mostrada en la figura). La incrustación del plano proyectivo también se puede formar a partir del dibujo pentagonal estándar del grafo de Petersen colocando una cruz dentro de la estrella de cinco puntas en el centro del dibujo y trazando las aristas de la estrella a través de esta cruz; el dibujo resultante tiene seis caras pentagonales. Esta construcción forma un mapa regular y demuestra que el grafo de Petersen tiene género no orientable 1.

El grafo de Petersen es fuertemente regular (con signatura srg(10,3,0,1) ). También es simétrico , lo que significa que es transitivo en aristas y en vértices . Más aún, es 3-arco-transitivo: todo camino dirigido de tres aristas en el grafo de Petersen puede transformarse en cualquier otro camino de este tipo mediante una simetría del grafo. ^{[ 7 ]} Es uno de los únicos 13 grafos cúbicos distancia-regulares . ^{[ 8 ]}

El grupo de automorfismos del grafo de Petersen es el grupo simétrico S ₅ ; la acción de S ₅ sobre el grafo de Petersen se deduce de su construcción como grafo de Kneser . El grafo de Petersen es un núcleo : todo homomorfismo del grafo de Petersen consigo mismo es un automorfismo . ^{[ 9 ]} Como se muestra en las figuras, los dibujos del grafo de Petersen pueden presentar simetría de cinco o tres vías, pero no es posible dibujar el grafo de Petersen en el plano de tal manera que el dibujo muestre el grupo de simetría completo del grafo.

A pesar de su alto grado de simetría, el grafo de Petersen no es un grafo de Cayley . Es el grafo transitivo de vértices más pequeño que no es un grafo de Cayley. ^{[ a ]}

El grafo de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano . Es el grafo cúbico sin puentes más pequeño que no tiene ciclo hamiltoniano. Es hipohamiltoniano , lo que significa que, aunque no tiene ciclo hamiltoniano, al eliminar cualquier vértice se convierte en hamiltoniano, y es el grafo hipohamiltoniano más pequeño.

Como grafo finito , conexo y transitivo por vértices que no posee un ciclo hamiltoniano, el grafo de Petersen constituye un contraejemplo a una variante de la conjetura de Lovász , pero la formulación canónica de la conjetura exige un camino hamiltoniano y es verificada por el grafo de Petersen.

Solo se conocen cinco grafos conexos transitivos por vértices sin ciclos hamiltonianos: el grafo completo K ₂ , el grafo de Petersen, el grafo de Coxeter y dos grafos derivados de los grafos de Petersen y Coxeter reemplazando cada vértice por un triángulo. ^{[ 8 ]} Si G es un grafo 2-conexo, r -regular con como máximo 3 r + 1 vértices, entonces G es hamiltoniano o G es el grafo de Petersen. ^{[ 10 ]}

Para comprobar que el grafo de Petersen no tiene ciclo hamiltoniano, consideremos las aristas del corte que desconectan el 5-ciclo interno del externo. Si existe un ciclo hamiltoniano C , este debe contener un número par de estas aristas. Si contiene solo dos, sus vértices extremos deben ser adyacentes en los dos 5-ciclos, lo cual es imposible. Por lo tanto, contiene exactamente cuatro. Supongamos que la arista superior del corte no está contenida en C (todos los demás casos son iguales por simetría). De las cinco aristas del ciclo externo, las dos superiores deben estar en C , las dos laterales no deben estar en C y, por lo tanto, la inferior debe estar en C. Las dos aristas superiores del ciclo interno deben estar en C , pero esto completa un ciclo no generador, que no puede formar parte de un ciclo hamiltoniano. Alternativamente, también podemos describir los grafos 3-regulares de diez vértices que sí tienen un ciclo hamiltoniano y demostrar que ninguno de ellos es el grafo de Petersen, encontrando en cada uno de ellos un ciclo más corto que cualquier ciclo en el grafo de Petersen. Cualquier grafo 3-regular hamiltoniano de diez vértices consta de un ciclo de diez vértices C más cinco cuerdas. Si alguna cuerda conecta dos vértices a distancia dos o tres a lo largo de C entre sí, el grafo tiene un ciclo 3 o 4, y por lo tanto no puede ser el grafo de Petersen. Si dos cuerdas conectan vértices opuestos de C con vértices a distancia cuatro a lo largo de C , hay nuevamente un ciclo 4. El único caso restante es una escalera de Möbius formada al conectar cada par de vértices opuestos mediante una cuerda, que nuevamente tiene un ciclo 4. Dado que el grafo de Petersen tiene circunferencia cinco, no puede formarse de esta manera y no tiene ciclo hamiltoniano.

El grafo de Petersen tiene número cromático 3, lo que significa que sus vértices pueden colorearse con tres colores —pero no con dos— de manera que ninguna arista conecte vértices del mismo color. Según el teorema de Brooks para coloraciones de listas, posee una coloración de listas con 3 colores.

El grafo de Petersen tiene índice cromático 4; colorear las aristas requiere cuatro colores. Como grafo cúbico conectado sin puentes con índice cromático cuatro, el grafo de Petersen es un snark . Es el snark más pequeño posible y fue el único snark conocido desde 1898 hasta 1946. El teorema del snark , un resultado conjeturado por WT Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, ^{[ 11 ]} afirma que todo snark tiene al grafo de Petersen como un menor .

Además, el gráfico tiene un índice cromático fraccional de 3, lo que demuestra que la diferencia entre el índice cromático y el índice cromático fraccional puede ser de hasta 1. La antigua conjetura de Goldberg-Seymour propone que esta es la mayor diferencia posible.

El número de Thue (una variante del índice cromático) del gráfico de Petersen es 5.

El grafo de Petersen requiere al menos tres colores en cualquier coloración (posiblemente impropia) que rompa todas sus simetrías; es decir, su número distintivo es tres. Excepto para los grafos completos, es el único grafo de Kneser cuyo número distintivo no es dos. ^{[ 12 ]}

El gráfico de Petersen:

• es 3-conexo y por lo tanto 3-arista-conexo y sin puente. Véase el glosario .
• tiene independencia número 4 y es tripartita. Véase el glosario .
• es cúbico , tiene número de dominancia 3 y tiene un emparejamiento perfecto y un factor 2 .
• tiene 6 combinaciones perfectas distintas.
• es el grafo cúbico más pequeño de circunferencia 5. (Es la única jaula (3,5) . De hecho, como solo tiene 10 vértices, es el único grafo de Moore (3,5) ). ^{[ 13 ]}
• Todo grafo cúbico sin puentes y sin menor de Petersen tiene una doble cobertura de ciclo. ^{[ 14 ]}
• es el grafo cúbico más pequeño con invariante de grafo de Colin de Verdière μ = 5 . ^{[ 15 ]}
• es el grafo más pequeño con número de policía 3. De hecho, es el único grafo de 10 vértices con número de policía 3. ^{[ 16 ] [ 17 ]}
• tiene radio 2 y diámetro 2. Es el grafo cúbico más grande con diámetro 2. ^{[ b ]}
• tiene 2000 árboles de expansión , la mayor cantidad de cualquier grafo cúbico de 10 vértices. ^{[ 18 ] [ 19 ] [ c ]}
• tiene polinomio cromático t ( t − 1)( t − 2)( t ⁷ − 12 t ⁶ + 67 t ⁵ − 230 t ⁴ + 529 t ³ − 814 t ² + 775 t − 352) . ^{[ 20 ]}
• tiene un polinomio característico ( t − 1) ⁵ ( t + 2) ⁴ ( t − 3) , lo que lo convierte en un grafo integral , un grafo cuyo espectro consta enteramente de números enteros.
• está saturado de H cuando H es K ₃ .

Un subgrafo euleriano de un grafo G es un subgrafo que consta de un subconjunto de las aristas de G , que tocan cada vértice de G un número par de veces. Estos subgrafos son los elementos del espacio de ciclos de G y a veces se denominan ciclos. Si G y H son dos grafos cualesquiera, una función de las aristas de G a las aristas de H se define como ciclo-continua si la preimagen de cada ciclo de H es un ciclo de G. Una conjetura de Jaeger afirma que todo grafo sin puentes tiene una aplicación ciclo-continua al grafo de Petersen. Jaeger demostró que esta conjetura implica la conjetura de la doble cobertura de 5 ciclos y la conjetura de Berge-Fulkerson. ^{[ 21 ]}

El grafo de Petersen generalizado G ( n , k ) se forma conectando los vértices de un n -gono regular con los vértices correspondientes de un polígono estrellado con el símbolo de Schläfli { n / k } . ^{[ 22 ] [ 23 ]} Por ejemplo, en esta notación, el grafo de Petersen es G (5,2) : se puede formar conectando los vértices correspondientes de un pentágono y una estrella de cinco puntas, y las aristas en la estrella conectan cada segundo vértice. Los grafos de Petersen generalizados también incluyen el n -prisma G ( n ,1) , el grafo de Dürer G (6,2) , el grafo de Möbius-Kantor G (8,3) , el dodecaedro G (10,2) , el grafo de Desargues G (10,3) , y el grafo de Nauru G (12,5) .

La familia de Petersen consta de los siete grafos que se pueden formar a partir del grafo de Petersen mediante cero o más aplicaciones de transformaciones Δ-Y o Y-Δ . El grafo completo K ₆ también pertenece a la familia de Petersen. Estos grafos forman los menores prohibidos para grafos incrustables sin enlaces , grafos que se pueden incrustar en el espacio tridimensional de tal manera que no haya dos ciclos en el grafo que estén enlazados . ^{[ 24 ]}

El grafo de Clebsch contiene muchas copias del grafo de Petersen como subgrafos inducidos : para cada vértice v del grafo de Clebsch, los diez no vecinos de v inducen una copia del grafo de Petersen.

• Exoo, Geoffrey; Harary, Frank ; Kabell, Jerald (1981), "Los números de cruce de algunos grafos de Petersen generalizados", Mathematica Scandinavica , 48 : 184–188 , doi : 10.7146/math.scand.a-11910.
• Lovász, László (1993), Problemas y ejercicios combinatorios (2ª  ed.), Holanda Septentrional, ISBN 0-444-81504-X.
• Schwenk, AJ (1989), "Enumeración de ciclos hamiltonianos en ciertos grafos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53– 59, doi : 10.1016/0095-8956(89)90064-6
• Zhang, Cun-Quan (1997), Flujos enteros y recubrimientos cíclicos de grafos , CRC Press, ISBN 978-0-8247-9790-4.
• Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs , Cambridge University Press, ISBN 978-0-5212-8235-2.

• Weisstein, Eric W. , "Petersen Graph" , MathWorld
• Gráfico de Petersen en la Enciclopedia en línea de secuencias de enteros