Gráfico de Petersen generalizado

Familia de grafos cúbicos formados a partir de polígonos regulares y estrellados

El grafo de Durero G (6, 2) .

En teoría de grafos , los grafos de Petersen generalizados son una familia de grafos cúbicos formados al conectar los vértices de un polígono regular con los vértices correspondientes de un polígono estrellado . Incluyen el grafo de Petersen y generalizan una de las formas de construir el grafo de Petersen. La familia de grafos de Petersen generalizados 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

${\displaystyle \{u_{0},u_{1},\ldots ,u_{n-1},v_{0},v_{1},\ldots ,v_{n-1}\}}$

y conjunto de bordes

${\displaystyle \{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\mid 0\leq i\leq n-1\}}$

donde los subíndices se deben leer módulo n y k < n /2. Algunos autores utilizan la notación GPG ( n , k ). La notación de Coxeter para el mismo grafo sería { n } + { n / k }, una combinación de los símbolos de Schläfli para el n -gono regular y el polígono estrellado a partir de los cuales se forma el grafo. El propio grafo de Petersen 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

Entre los grafos de Petersen generalizados se encuentran el prisma n 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 grafo de Desargues G (10, 3) y el grafo de Nauru G (12, 5).

Cuatro grafos de Petersen generalizados – el de 3 prismas, el de 5 prismas, el grafo de Durero y G (7, 2) – se encuentran entre los siete grafos que son cúbicos , conexos por 3 vértices y bien cubiertos (lo que significa que todos sus conjuntos independientes máximos tienen el mismo tamaño). ^[4]

Propiedades

Uno de los tres ciclos hamiltonianos en G (9, 2). Los otros dos ciclos hamiltonianos en el mismo gráfico son simétricos bajo rotaciones de 40° del dibujo.

Esta familia de grafos posee varias propiedades interesantes. Por ejemplo:

• G ( n , k ) es transitivo-vertical (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 ²  ≡ ±1 (mod  n ).
• G ( n , k ) es transitivo en cuanto a aristas (tiene simetrías que llevan cualquier arista a cualquier otra arista) solo en los siguientes siete casos: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). ^[5] Por lo tanto, estos siete grafos son los únicos grafos de Petersen generalizados simétricos .
• G ( n , k ) es bipartito si y sólo si n es par y k es impar.
• G ( n , k ) es un gráfico de Cayley si y solo si k ²  ≡ 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 grafos 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]
• Todo gráfico de Petersen generalizado es un gráfico de distancia unitaria . ^[9]

Isomorfismos

G ( n , k ) es isomorfo a G ( n , l ) si y sólo si k=l o kl  ≡ ±1 (mod  n ). ^[10]

Circunferencia

La circunferencia de G ( n , k ) es al menos 3 y como máximo 8, en particular: ^[11]

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

Una tabla con valores exactos de circunferencia:

Número cromático e índice cromático

Los grafos de Petersen generalizados son grafos regulares de grado tres, por lo que según el teorema de Brooks su número cromático sólo puede ser dos o tres. Más exactamente:

${\displaystyle \chi (G(n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\\\end{cases}}}$

Donde denota el AND lógico , mientras que el OR lógico . Aquí, denota divisibilidad y denota su negación. Por ejemplo, el número cromático de es 3. ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \mid }$ ${\displaystyle \nmid }$ ${\displaystyle G(5,2)}$

• 
  Una coloración triple del gráfico de Petersen o ${\displaystyle G(5,2)}$
• 
  Una coloración doble del gráfico de Desargues o ${\displaystyle G(10,3)}$
• 
  Una coloración en 3 colores del gráfico de Durero o ${\displaystyle G(6,2)}$

El grafo de Petersen , al ser un snark , tiene un índice cromático de 4: sus aristas requieren cuatro colores. Todos los demás grafos de Petersen generalizados tienen un índice cromático de 3. Éstas son las únicas posibilidades, según el teorema de Vizing . ^[12]

El gráfico de Petersen generalizado G (9, 2) es uno de los pocos gráficos conocidos que tiene solo una coloración de 3 aristas . ^[13]

• 
  Una coloración de 4 aristas del gráfico de Petersen o ${\displaystyle G(5,2)}$
• 
  Una coloración de tres aristas del gráfico de Durero o ${\displaystyle G(6,2)}$
• 
  Una coloración de 3 aristas del dodecaedro o ${\displaystyle G(10,2)}$
• 
  Una coloración de 3 aristas del gráfico de Desargues o ${\displaystyle G(10,3)}$
• 
  Una coloración de tres aristas del gráfico de Nauru o ${\displaystyle G(12,5)}$

El gráfico de Petersen en sí es el único gráfico de Petersen generalizado que no es coloreable en tres aristas . ^[14]

Coloraciones perfectas

Se enumeran todas las matrices admisibles de todas las 2-coloraciones perfectas de los grafos G ( n , 2 ) y G ( n , 3 ). ^[15]

Referencias

1. Coxeter, HSM (1950), "Configuraciones autoduales y grafos regulares", Boletín de la Sociedad Matemática Americana , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
2. Watkins, Mark E. (1969), "Un teorema sobre coloraciones de Tait con una aplicación a los gráficos generalizados de Petersen", Journal of Combinatorial Theory , 6 (2): 152–164, doi : 10.1016/S0021-9800(69)80116-X.
3. Gross, Jonathan L.; Tucker, Thomas W. (1987), Teoría de grafos topológicos , Nueva York: Wiley. Ejemplo 2.1.2, pág.58.
4. 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.
5. Frucht, R. ; Graver, JE; Watkins, ME (1971), "Los grupos de los grafos de Petersen generalizados", Actas de la Sociedad Filosófica de Cambridge , 70 (2): 211–218, doi :10.1017/S0305004100049811.
6. Alspach, BR (1983), "La clasificación de los grafos de Petersen generalizados hamiltonianos", Journal of Combinatorial Theory , Serie B, 34 (3): 293–312, doi : 10.1016/0095-8956(83)90042-4 , MR  0714452.
7. Thomason, Andrew (1982), "Los gráficos cúbicos con tres ciclos hamiltonianos no siempre son coloreables de manera única por sus bordes", Journal of Graph Theory , 6 (2): 219–221, doi :10.1002/jgt.3190060218.
8. Schwenk, Allen J. (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 , MR  1007713.
9. Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidades de distancia (PDF) , preimpresiones de IMFM, vol. 1109, archivado desde el original (PDF) el 24 de julio de 2018 , consultado el 7 de abril de 2017.
10. Steimle, Alice; Staton, William (2009), "Las clases de isomorfismo de los grafos de Petersen generalizados", Discrete Mathematics , 309 (1): 231–237, doi : 10.1016/j.disc.2007.12.074
11. Ferrero, Daniela ; Hanusch, Sarah (2014), "Conectividad de componentes de grafos generalizados de Petersen" (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
12. Castagna, Frank; Prins, Geert Caleb Ernst (1972), "Cada gráfico de Petersen generalizado tiene una coloración de Tait", Pacific Journal of Mathematics , 40 (1): 53–58, doi : 10.2140/pjm.1972.40.53 , ISSN  0030-8730, MR  0304223, Zbl  0236.05106
13. Bollobás, Béla (2004), Teoría de grafos extremos , Dover, p. 233. Reimpresión de la edición de Academic Press de 1978.
14. Castagna, Frank; Prins, Geert (1972), "Cada gráfico de Petersen generalizado tiene una coloración de Tait", Pacific Journal of Mathematics , 40 : 53–58, doi : 10.2140/pjm.1972.40.53.
15. Karami, Hamed (2022), "Coloraciones bidimensionales perfectas del gráfico generalizado de Petersen GP(n,3)", Revista electrónica de teoría de grafos y aplicaciones , 10 : 239–245, arXiv : 2009.07120 , doi : 10.5614/ejgta.2022.10.1.16.