Grafo de Petersen generalizado

En teoría de grafos , los grafos de Petersen generalizados son una familia de grafos cúbicos formados al conectar los vértices de un polígono regular con los vértices correspondientes de un polígono estrellado . Incluyen el grafo de Petersen y generalizan una de las formas de construirlo. La familia de grafos de Petersen generalizados fue introducida en 1950 por HSM Coxeter ^{[ 1 ]} y recibió su nombre en 1969 de Mark Watkins ^{[ 2 ] .}

En la notación de Watkins,${\displaystyle G(n,k)}$es un grafo con 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${\displaystyle n}$y dónde${\displaystyle k<n/2}$Algunos autores utilizan la notación${\displaystyle GPG(n,k)}$La notación de Coxeter para el mismo gráfico sería:${\displaystyle \{n\}+\{n/k\}}$, una combinación de los símbolos de Schläfli para el n -gono regular y el polígono estrellado a partir del cual se forma el grafo. El grafo de Petersen en sí es${\displaystyle G(5,2)}$o${\displaystyle \{5\}+\{5/2\}}$Algunos autores también permiten${\displaystyle k=n/2}$, produciendo un gráfico que no es un gráfico regular . ^{[ 3 ]}

Cualquier grafo de Petersen generalizado también puede construirse a partir de un grafo de voltaje con dos vértices, dos bucles propios y otra arista. ^{[ 4 ]}

Entre los grafos de Petersen generalizados se encuentran los${\displaystyle n}$-prisma${\displaystyle G(n,1)}$, el gráfico de Durero${\displaystyle G(6,2)}$, el gráfico de Möbius-Kantor${\displaystyle G(8,3)}$, el dodecaedro${\displaystyle G(10,2)}$, el gráfico de Desargues${\displaystyle G(10,3)}$y el gráfico de Nauru${\displaystyle G(12,5)}$.

Cuatro grafos de Petersen generalizados: el prisma de 3, el prisma de 5, el grafo de Dürer y${\displaystyle G(7,2)}$– se encuentran entre los siete grafos que son cúbicos , conexos por 3 vértices y bien cubiertos (lo que significa que todos sus conjuntos independientes máximos tienen el mismo tamaño). ^{[ 5 ]}

Esta familia de grafos posee una serie de propiedades interesantes. Por ejemplo:

• ${\displaystyle G(n,k)}$es transitiva en vértices (lo que significa que tiene simetrías que llevan cualquier vértice a cualquier otro vértice) si y solo si${\displaystyle (n,k)=(10,2)}$o${\displaystyle k^{2}\equiv \pm 1\ (\mathrm {mod} \ n)}$.
• ${\displaystyle G(n,k)}$es transitiva por aristas (tiene simetrías que llevan cualquier arista a cualquier otra arista) solo en los siguientes siete casos:${\displaystyle (n,k)}$es (4, 1) , (5, 2) , (8, 3) , (10, 2) , (10, 3) , (12, 5) o (24, 5). ^{[ 6 ]} Por lo tanto, estos siete grafos son los únicos grafos de Petersen generalizados simétricos .
• ${\displaystyle G(n,k)}$es bipartita si y solo si${\displaystyle n}$es par y${\displaystyle k}$es extraño.
• ${\displaystyle G(n,k)}$es un gráfico de Cayley si y solo si${\displaystyle k^{2}\equiv 1\ (\mathrm {mod} \ n)}$.
• ${\displaystyle G(n,k)}$es hipohamiltoniano cuando${\displaystyle n}$es congruente con 5 módulo 6 y${\displaystyle k}$es 2,${\displaystyle n-2}$, o${\displaystyle (n\pm 1)/2}$(estas cuatro elecciones de k conducen a grafos isomorfos). También es no hamiltoniano cuando${\displaystyle n}$es divisible por 4, al menos igual a 8 y${\displaystyle k=n/2}$. En todos los demás casos tiene un ciclo hamiltoniano . ^{[ 3 ]} Cuando${\displaystyle n}$es congruente con 3 módulo  6,${\displaystyle G(n,2)}$tiene exactamente tres ciclos hamiltonianos. ^{[ 7 ]} Para${\displaystyle G(n,2)}$, el número de ciclos hamiltonianos se puede calcular mediante una fórmula que depende de la clase de congruencia de${\displaystyle n}$módulo 6 e involucra los números de Fibonacci . ^{[ 8 ]} También se han encontrado relaciones de recurrencia lineales para el número de ciclos hamiltonianos para${\displaystyle G(n,3)}$y${\displaystyle G(n,4)}$. ^{[ 9 ]}
• Todo grafo de Petersen generalizado es un grafo de distancia unitaria . ^{[ 10 ]}