Gráfico de Petersen generalizado

En teoría de grafos, un gráfico de Petersen generalizado es una familia de gráficos cúbicos formados al conectar los vértices de un polígono regular con los vértices correspondientes de una estrella . La familia incluye el gráfico de Petersen y generaliza una de las formas de construir el gráfico de Petersen. La familia de gráficos de Petersen generalizados fue introducida en 1950 por Coxeter [1] y estos gráficos fueron nombrados en 1969 por Mark Watkins [2] .

Definición y denominación

En la notación de Watkins , G ( n , k ) es un gráfico de conjunto de vértices

{ tu 0 , tu 1 , ..., tu norte −1 , v 0 , v 1 , ... , v norte −1 }

y muchas costillas

{ tu yo tu yo +1 , tu yo v yo , v yo v yo + k : yo  = 0,..., norte  - 1 }

donde los índices se toman módulo n y k < n /2. La notación de Coxeter para el mismo gráfico sería { n }+{ n/k }, una combinación del símbolo de Schläfli para un n - gon regular y la estrella a partir de la cual se forma el gráfico. Cualquier gráfico de Petersen generalizado se puede construir como un gráfico de tensión a partir de un gráfico con dos vértices, dos bucles y una arista más [3] .

El gráfico de Petersen en sí es G (5,2) o {5}+{5/2}.

Ejemplos

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-Cantor G (8,3), el dodecaedro G (10,2), el de Desargues gráfico G (10,3) y Conde Nauru G (12,5).

Los cuatro gráficos de Petersen generalizados, el prisma triangular, el prisma de 5 gonales, el gráfico de Durero y G (7,2), están en siete gráficos que son cúbicos , conectados por 3 vértices y bien cubiertos (lo que significa que todos de sus conjuntos independientes más grandes tienen un mismo tamaño) [4] .

Propiedades

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

  1. G ( n , k ) es de vértice transitivo (lo que significa que hay simetrías que llevan cualquier vértice a cualquier otro) si y solo si n  = 10 y k  = 2 o si k 2  ≡ ±1 (mod  n ).
  2. Es de borde transitivo (tiene simetrías que asignan cualquier borde a cualquier otro) solo en los siguientes siete casos: ( n , k ) = (4.1), (5.2), (8.3), (10.2 ), (10.3), ( 12.5), (24.5) [5] . Solo estos siete gráficos son gráficos de Petersen generalizados simétricos .
  3. Es bipartito si y solo si n es par y k es impar.
  4. Es un gráfico de Cayley si y sólo si k 2  ≡ 1 (mod  n ).
  5. Es hipo -hamiltoniano si n es congruente con 5 módulo 6 y k es igual a 2, n − 2, ( n + 1)/2, o ( n − 1)/2 (los cuatro valores de k conducen a gráficos isomorfos). No es hamiltoniano si n es divisible por cuatro, al menos cuando vale 8, yk es igual a n /2. En todos los demás casos tiene un ciclo hamiltoniano [6] . Si n es congruente con 3 módulo 6 y k es 2, G ( n , k ) tiene exactamente tres ciclos hamiltonianos [7] , para G ( n ,2) el número de ciclos hamiltonianos se puede calcular mediante una fórmula dependiendo de las clases de n módulo seis , e involucra números de Fibonacci [8] .

El gráfico de Petersen es el único gráfico de Petersen generalizado que no se puede teñir de borde con 3 colores [9] . El gráfico de Petersen generalizado G (9,2) es uno de los pocos gráficos conocidos que no pueden colorearse en los bordes con 3 colores [10] .

Cualquier gráfico de Petersen generalizado es un gráfico de unidad de distancia [11] .

Notas

  1. ↑ HSM Coxeter. Configuraciones autoduales y gráficos regulares // Boletín de la Sociedad Matemática Estadounidense . - 1950. - T. 56 . - S. 413-455 . -doi : 10.1090 / S0002-9904-1950-09407-5 .
  2. ↑ Mark E. Watkins. Un teorema sobre los colorantes de Tait con una aplicación a los gráficos de Petersen generalizados // Revista de teoría combinatoria . - 1969. - T. 6 . - S. 152-164 . -doi : 10.1016 / S0021-9800(69)80116-X .
  3. ↑ Jonathan L. Gross, Thomas W. Tucker. Ejemplo 2.1.2. // Teoría de grafos topológicos . - Nueva York: Wiley, 1987. - Pág  . 58 .
  4. ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. Una caracterización de gráficos cúbicos bien cubiertos // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . - S. 193-212 .
  5. ↑ R. Frucht, J. E. Graver, M. E. Watkins. Los grupos del Graf Petersen generalizado // Actas de la Sociedad Filosófica de Cambridge . - 1971. - T. 70 . - S. 211-218 . -doi : 10.1017/ S0305004100049811 .
  6. ↑ BR Alspach. La clasificación de grafos de Petersen generalizados hamiltonianos // Journal of Combinatorial Theory, Serie B. - 1983. - V. 34 . - S. 293-312 . - doi : 10.1016/0095-8956(83)90042-4 .
  7. ↑ Andrew Thomason. Los gráficos cúbicos con tres ciclos hamiltonianos no siempre son únicamente coloreables en los bordes  // Journal of Graph Theory. - 1982. - T. 6 , núm. 2 . - S. 219-221 . -doi : 10.1002 / jgt.3190060218 .
  8. ↑ Allen J. Schwenk. Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados // Journal of Combinatorial Theory . - 1989. - T. 47 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
  9. ↑ Frank Castagna, Geert Prins. Cada gráfico de Petersen generalizado tiene un Tait Coloring // Pacific Journal of Mathematics . - 1972. - T. 40 .
  10. ↑ Bella Bollobas. Teoría de Grafos Extrema. - Dover, 2004. - Pág. 233. Edición reimpresa de 1978 Academic Press
  11. ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia. - 2010. - T. 1109 .