Gráfico de Petersen generalizado

Familia de gráficos cúbicos formados a partir de polígonos regulares y estrellados.

El gráfico de Durero G (6, 2) .

En teoría de grafos , los gráficos de Petersen generalizados son una familia de gráficos cúbicos formados conectando los vértices de un polígono regular a los vértices correspondientes de un polígono estrella . Incluyen el gráfico de Petersen y generalizan una de las formas de construir el gráfico de Petersen. La familia de gráficos generalizados de Petersen 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 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 n -gón regular y el polígono estrella a partir de los cuales 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 automáticos y otro borde. ^[3]

Ejemplos

Entre los gráficos de Petersen generalizados se encuentran el n -prisma G ( n , 1), el gráfico de Durero G (6, 2), el gráfico 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 G de Nauru (12, 5).

Cuatro gráficas generalizadas de Petersen (la de 3 prismas, la de 5 prismas, la gráfica de Durero y G (7, 2)) se encuentran entre las siete gráficas que son cúbicas , conectadas por 3 vértices y bien cubiertas (lo que significa que todas de 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 gráficos posee una serie de propiedades interesantes. Por ejemplo:

• G ( n , k ) es transitiva de 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 ²  ≡ ±1 (mod  n ) .
• G ( n , k ) es transitivo de 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 tanto, los únicos gráficos de Petersen generalizados simétricos .
• G ( n , k ) es bipartita si y solo 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 gráficas isomorfas). 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.

Al ser regulares , según el teorema de Brooks su número cromático no puede ser mayor que su grado . Las gráficas de Petersen generalizadas son cúbicas, por lo que su número cromático puede ser 2 o 3. 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 . Por ejemplo, el número cromático de es 3. ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle G(5,2)}$

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

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 generalizado de Petersen G (9, 2) es uno de los pocos gráficos que se sabe que tiene una sola coloración de 3 aristas . ^[13]

• 
  Una coloración de 4 bordes del gráfico de Petersen o ${\displaystyle G(5,2)}$
• 
  Una coloración de 3 bordes del gráfico de Durero o ${\displaystyle G(6,2)}$
• 
  Una coloración de 3 bordes del dodecaedro o ${\displaystyle G(10,2)}$
• 
  Una coloración de 3 bordes del gráfico de Desargues o ${\displaystyle G(10,3)}$
• 
  Una coloración de 3 bordes 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 se puede colorear en 3 aristas . ^[14]

Colorantes perfectos

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

Referencias

1. Coxeter, HSM (1950), "Configuraciones autoduales y gráficos regulares", Boletín de la Sociedad Matemática Estadounidense , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
2. Watkins, Mark E. (1969), "Un teorema sobre coloraciones 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.
3. Bruto, Jonathan L.; Tucker, Thomas W. (1987), Teoría de grafos topológicos , Nueva York: Wiley. Ejemplo 2.1.2, p.58.
4. Campbell, SR; Ellingham, Minnesota ; Royle, Gordon F. (1993), "Una caracterización de gráficas cúbicas bien cubiertas", Journal of Combinatorial Mathematics and Combinatorial Computing , 13 : 193–212, MR  1220613.
5. Frucht, R .; Graver, JE; Watkins, ME (1971), "Los grupos de los gráficos generalizados de Petersen", 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 gráficos de Petersen generalizados hamiltonianos", Journal of Combinatorial Theory , Serie B, 34 (3): 293–312, doi : 10.1016/0095-8956(83)90042-4 , SEÑOR  0714452.
7. Thomason, Andrew (1982), "Los gráficos cúbicos con tres ciclos hamiltonianos no siempre se pueden colorear de forma única", 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 gráficos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064 -6 , señor  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.
10. Steimle, Alicia; Staton, William (2009), "Las clases de isomorfismo de los gráficos de Petersen generalizados", Matemáticas discretas , 309 (1): 231–237, doi : 10.1016/j.disc.2007.12.074
11. 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 original (PDF) el 2018-10-20 , consultado el 2018-10-20
12. Castaña, Frank; Prins, Geert Caleb Ernst (1972), "Cada gráfico de Petersen generalizado tiene una coloración Tait", Pacific Journal of Mathematics , 40 (1): 53–58, doi : 10.2140/pjm.1972.40.53 , ISSN  0030-8730, SEÑOR  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. Castaña, Frank; Prins, Geert (1972), "Cada gráfico de Petersen generalizado tiene una coloración Tait", Pacific Journal of Mathematics , 40 : 53–58, doi : 10.2140/pjm.1972.40.53.
15. Karami, Hamed (2022), "2 colores perfectos del gráfico generalizado de Petersen GP (n, 3)", Electronic Journal of Graph Theory and Applications , 10 : 239–245, arXiv : 2009.07120 , doi : 10.5614/ejgta. 2022.10.1.16.