En teoría de grafos , los grafos de Petersen generalizados son una familia de grafos cúbicos formados conectando los vértices de un polígono regular con los vértices correspondientes de un polígono de estrella . Incluyen el gráfico de Petersen y generalizan una de las formas de construir el gráfico de Petersen. La familia de grafos de Petersen generalizada fue introducida en 1950 por HSM Coxeter [1] y recibió su nombre en 1969 por Mark Watkins. [2]
Definición y notación
En la notación de Watkins, G ( n , k ) es un gráfico con un conjunto de vértices
y conjunto de bordes
donde los subíndices deben leerse módulo n y k < n / 2. Algunos autores utilizan la notación GPG ( n , k ). La notación de Coxeter para el mismo gráfico sería { n } + { n / k }, una combinación de los símbolos de Schläfli para el polígono regular de n -gon y estrella a partir del cual se forma el gráfico. El gráfico de Petersen en sí es G (5, 2) o {5} + {5/2}.
Cualquier gráfico de Petersen generalizado también se puede construir a partir de un gráfico de voltaje con dos vértices, dos bucles propios y otro borde. [3]
Ejemplos de
Entre los grafos de Petersen generalizados se encuentran el n -prisma G ( n , 1), el grafo de Durero G (6, 2), el grafo de Möbius-Kantor G (8, 3), el dodecaedro G (10, 2), el gráfico de Desargues el gráfico G (10, 3) y el gráfico de Nauru G (12, 5).
Cuatro gráficos de Petersen generalizados - el de 3 prismas, el de 5 prismas, el gráfico de Durero y G (7, 2) - se encuentran entre los siete gráficos que son cúbicos , están conectados con 3 vértices y están bien cubiertos (lo que significa que todos de sus conjuntos independientes máximos tienen el mismo tamaño). [4]
Propiedades
Esta familia de gráficos posee varias propiedades interesantes. Por ejemplo:
- G ( n , k ) es transitivo por vértice (lo que significa que tiene simetrías que llevan cualquier vértice a cualquier otro vértice) si y solo si ( n , k ) = (10, 2) o k 2 ≡ ± 1 (mod n ) .
- G ( n , k ) es transitivo por el borde (tiene simetrías que llevan cualquier borde a cualquier otro borde) solo en los siguientes siete casos: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). [5] Estos siete gráficos son, por lo tanto, los únicos gráficos de Petersen generalizados simétricos .
- G ( n , k ) es bipartito si y solo si n es par y k es impar.
- G ( n , k ) es una gráfica de Cayley si y solo si k 2 ≡ 1 (mod n ).
- G ( n , k ) es hipohamiltoniano cuando n es congruente con 5 módulo 6 y k = 2, n - 2 o ( n ± 1) / 2 (estas cuatro opciones de k conducen a gráficos isomorfos). También es no hamiltoniano cuando n es divisible por 4, al menos igual a 8, y k = n / 2. En todos los demás casos tiene un ciclo hamiltoniano . [6] Cuando n es congruente con 3 módulo 6 G ( n , 2) tiene exactamente tres ciclos hamiltonianos. [7] Para G ( n , 2), el número de ciclos hamiltonianos se puede calcular mediante una fórmula que depende de la clase de congruencia de n módulo 6 e involucra los números de Fibonacci . [8]
- Cada gráfico de Petersen generalizado es un gráfico de unidad de distancia . [9]
Isomorfismos
G ( n , k ) es isomorfo a G ( n , l ) si y solo si kl ≡ ± 1 (mod n ). [10]
Circunferencia
La circunferencia de G ( n , k ) es al menos 3 y como máximo 8, en particular: [11]
Una tabla con valores de circunferencia exactos:
Condición Circunferencia 3 4 5 6 7 de lo contrario 8
Número cromático e índice cromático
Al ser regular , según el teorema de Brooks, su número cromático no puede ser mayor que su grado . Los gráficos de Petersen generalizados son cúbicos, por lo que su número cromático puede ser 2 o 3. Más exactamente:
Dónde denota el AND lógico , mientras queel OR lógico . Por ejemplo, el número cromático de es 3.
Una 3 coloración del gráfico de Petersen o
Una coloración 2 del gráfico de Desargues o
3 colores del gráfico de Durero o
El gráfico de Petersen , al ser un snark , tiene un índice cromático de 4. Todos los demás gráficos de Petersen generalizados tienen un índice cromático de 3. [12]
El gráfico de Petersen generalizado G (9, 2) es uno de los pocos gráficos que se sabe que tiene solo una coloración de 3 bordes . [13]
Una coloración de 4 bordes del gráfico de Petersen o
Una coloración de 3 bordes del gráfico de Durero o
Una coloración de 3 bordes del dodecaedro o
Una coloración de 3 bordes del gráfico de Desargues o
Una coloración de 3 bordes del gráfico de Nauru o
El gráfico de Petersen en sí es el único gráfico de Petersen generalizado que no se puede colorear en 3 bordes . [14]
Referencias
- ^ Coxeter, HSM (1950), "Configuraciones auto-duales y gráficos regulares", Boletín de la American Mathematical Society , 56 (5): 413–455, doi : 10.1090 / S0002-9904-1950-09407-5.
- ^ Watkins, Mark E. (1969), "Un teorema sobre coloraciones de Tait con una aplicación a los gráficos de Petersen generalizados", Journal of Combinatorial Theory , 6 (2): 152-164, doi : 10.1016 / S0021-9800 (69) 80116 -X.
- ^ Gross, Jonathan L .; Tucker, Thomas W. (1987), Topological Graph Theory , Nueva York: Wiley. Ejemplo 2.1.2, p.58.
- ^ Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993), "Una caracterización de gráficos cúbicos bien cubiertos", Journal of Combinatorial Mathematics and Combinatorial Computing , 13 : 193-212, MR 1220613.
- ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society , 70 (2): 211-218, doi : 10.1017 / S0305004100049811.
- ^ Alspach, BR (1983), "La clasificación de los gráficos de Petersen generalizados de Hamilton", Journal of Combinatorial Theory, Serie B , 34 (3): 293–312, doi : 10.1016 / 0095-8956 (83) 90042-4 , MR 0714452.
- ^ Thomason, Andrew (1982), "Las gráficas cúbicas con tres ciclos hamiltonianos no siempre son únicamente coloreables en los bordes", Journal of Graph Theory , 6 (2): 219-221, doi : 10.1002 / jgt.3190060218.
- ^ Schwenk, Allen J. (1989), "Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53-59, doi : 10.1016 / 0095-8956 (89) 90064- 6 , MR 1007713.
- ^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia (PDF) , preimpresiones de IMFM, 1109.
- ^ Steimle, Alice; Staton, William (2009), "Las clases de isomorfismo de los grafos de Petersen generalizados", Matemáticas discretas , 309 (1): 231-237, doi : 10.1016 / j.disc.2007.12.074
- ^ Ferrero, Daniela; Hanusch, Sarah (2014), "Conectividad de componentes de gráficos de Petersen generalizados" (PDF) , International Journal of Computer Mathematics , 91 (9): 1940-1963, doi : 10.1080 / 00207160.2013.878023 , ISSN 0020-7160 , archivado desde el original (PDF) el 2018-10-20 , consultado el 2018-10-20
- ^ Castagna, Frank; Prins, Geert Caleb Ernst (1972), "Todo gráfico de Petersen generalizado tiene un color Tait", Pacific Journal of Mathematics , 40 (1): 53–58, doi : 10.2140 / pjm.1972.40.53 , ISSN 0030-8730 , MR 0304223 , Zbl 0236.05106
- ^ Bollobás, Béla (2004), Teoría de grafos extremos , Dover, p. 233. Reimpresión de la edición de 1978 Academic Press.
- ^ Castagna, Frank; Prins, Geert (1972), "Cada gráfico de Petersen generalizado tiene un color Tait", Pacific Journal of Mathematics , 40 : 53–58, doi : 10.2140 / pjm.1972.40.53.