Grafo de Petersen generalizado

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]

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]

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

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

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]