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,. y Mark Watkins les dio en 1969 el nombre que ahora llevan..

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

y un conjunto de aristas

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.. Example 2.1.2, p.58.

Ejemplos miniaturadeimagen|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)..

Propiedades

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 k2 ≡ ±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).. 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 k2 ≡ 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.. Cuando n es congruente con 3 módulo 6 G(n, 2) tiene exactamente tres ciclos hamiltonianos.. 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.. Todo grafo de Petersen generalizado es un grafo de distancia unitaria..

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

Cintura La cintura de G(n, k) es al menos 3 y como máximo 8, en particular:

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

CondiciónCintura34567de lo contrario8

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:

Donde denota el operador lógico Y, mientras que es el operador lógico O disyuntivo. Por ejemplo, el número cromático de es 3.

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.

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.. Reprint of 1978 Academic Press edition.

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

Referencias

Categoría:Familias paramétricas de grafos Categoría:Grafos regulares