Grafo de Petersen generalizado

En teoría de grafos, los grafos de Petersen generalizados son una familia de grafos cúbicos formada al conectar los vértices de un polígono regular con los vértices correspondientes de un estrella. Incluyen el grafo de Petersen y generalizan una de las formas de construir el grafo de Petersen. La familia de grafos de Petersen generalizada fue introducida en 1950 por Harold Scott MacDonald Coxeter,^[1] y Mark Watkins les dio en 1969 el nombre que ahora llevan.^[2]

El grafo de Durero G(6, 2)

Definición y notación

En la notación de Watkins, G(n, k) es un grafo con un conjunto de vértices

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

y un conjunto de aristas

${\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 grafo sería {n} + {n/k}, una combinación de los símbolos de Schläfli para n-gonos regulares y estrellas a partir de los cuales se forma el grafo. El grafo de Petersen en sí es G(5, 2) o {5} + {5/2}.

Cualquier grafo de Petersen generalizado también se puede construir a partir de un grafo de voltage con dos vértices, dos auto bucles y otra arista.^[3]

Ejemplos

El 8-prisma G(8, 1).

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 grafo dodecaédrico 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, 3-vértices-conectado y bien recubierto (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 vértices-transitivo (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 aristas-transitivo (que 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] Estos siete grafos son, por lo tanto, los únicos grafos de Petersen generalizados symmetric.
• G(n, k) es bipartito si y solo si n es par y k es impar.
• G(n, k) es un grafo 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). Tampoco es hamiltoniano cuando n es divisible por 4, al menos igual a 8, y k = n/2. En todos los demás casos posee un camino 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 a una sucesión de Fibonacci.^[8]
• Todo grafo de Petersen generalizado es un grafo de distancia unitaria.^[9]

Isomorfismos

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

Cintura

La cintura 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\}.}$

A continuación figura una tabla con valores de cintura exactos:

Condición	Cintura
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
de lo contrario	8

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

Siendo regular, según el teorema de Brooks su coloración no puede ser mayor que su grado. Los grafos de Petersen generalizados son cúbicos, 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 ${\displaystyle \land }$ denota el operador lógico Y, mientras que ${\displaystyle \lor }$ es el operador lógico O disyuntivo. Por ejemplo, el número cromático de ${\displaystyle G(5,2)}$ es 3.

• 
  Un 3-coloreado del grafo de Petersen o ${\displaystyle G(5,2)}$
• 
  Un 2-coloreado del grafo de Desargues o ${\displaystyle G(10,3)}$
• 
  Un 3-coloreado del grafo de Durero o ${\displaystyle G(6,2)}$

El grafo de Petersen, siendo un snark, tiene un índice cromático de 4. Todos los demás grafos de Petersen generalizados tienen un índice cromático de 3.^[12]

El grafo de Petersen generalizado G(9, 2) es uno de los pocos grafos que se sabe que tiene solo un único 3-aristas-coloreado.^[13]

• 
  Un 4-aristas-coloreado del grafo de Petersen o ${\displaystyle G(5,2)}$
• 
  Un 3-aristas-coloreado del grafo de Durero o ${\displaystyle G(6,2)}$
• 
  Un 3-aristas-coloreado del grafo dodecaédrico o ${\displaystyle G(10,2)}$
• 
  Un 3-aristas-coloreado del grafo de Desargues o ${\displaystyle G(10,3)}$
• 
  Un 3-aristas-coloreado del grafo de Nauru o ${\displaystyle G(12,5)}$

El grafo de Petersen en sí es el único grafo de Petersen generalizado que no es 3-aristas-coloreable.^[14]