Grafo de Petersen generalizado

Em teoria dos grafos, os grafos de Petersen generalizados são uma família de grafos cúbicos formados pela conexão de vértices de um polígono regular para os vértices correspondentes de um polígono estrela. Eles incluem o grafo de Petersen e generalizam uma das formas de construir o grafo de Petersen. A família dos grafos de Petersen generalizados foi introduzida em 1950 por H. S. M. Coxeter e estes grafos receberam seu nome em 1969 por Mark Watkins.

O grafo de Dürer G(6,2).

Definição e notação

Na notação de Watkins, G(n,k) é um grafo com conjunto de vértices

{u₀, u₁, ..., u_n−1, v₀, v₁, ..., v_n−1}

e conjunto de arestas

{u_i u_i+1, u_i v_i, v_i v_i+k: i = 0,...,n − 1}

onde os subscritos devem ser lidos modulo n e k < n/2. A notação de Coxeter para o mesmo grafo seria {n}+{n/k}, uma combinação dos símbolos de Schläfli para o n-gono regular e o polígono estrela a partir do qual o grafo é formado. Qualquer grafo de Petersen generalizado também pode ser construído como um grafo de tensão a partir de um grafo com dois vértices, dois auto-laços, e uma outra aresta^{Exemplo 2.1.2, p. 58.}

O grafo de Petersen em si é G(5,2) ou {5}+{5/2}.

Exemplos

Entre os grafos de Petersen generalizados estão os n-prismas G(n,1) o grafo de Dürer G(6,2), o grafo de Möbius-Kantor G(8,3), o dodecaedro G(10,2), o grafo de Desargues G(10,3) e o grafo de Nauru G(12,5).

Propriedades

Um dos três ciclos hamiltonianos em G(9,2). Os outros dois ciclos hamiltonianos em um mesmo grafo são simétricos abaixo de 40° rotações do desenho.

Esta família de grafos possui um número de propriedades interessantes. Por exemplo,

1. G(n,k) é vértice-transitivo (o que significa que ele tem simetrias que levam qualquer vértice para qualquer outro vértice)se e somente se n = 10 e k =2 ou se k² ≡ ±1 (mod n).
2. Ele é aresta-transitivo (tendo simetrias que levam qualquer aresta para qualquer outra aresta) apenas nos seguintes sete casos: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Estes sete grafos são, portanto, os únicos grafos de Petersen generalizados simétricos.
3. Ele é bipartido se e somente se n é par e k é ímpar.
4. Ele é um grafo de Cayley se e somente se k² ≡ 1 (mod n).
5. Ele é hipohamiltoniano quando n é congruente a 5 módulo 6 e k é 2, n−2, (n+1)/2, ou (n−1)/2 (todos essas quatro escolhas de k levam a grafos isomórficos). Ele é também não-Hamiltoniano quando n é divisível por quatro, pelo menos igual a 8, w k é n/2. Em todos os outros casos ele tem um ciclo hamiltoniano.

Quando n é congruente a 3 modulo 6 e k is 2, G(n,k) tem exatamente três ciclos hamiltonianos.

O grafo de Petersen em si é o único grafo de Petersen generalizado que não é 3-aresta colorível.

Todo grafo de Petersen generalizado é um grafo distância-unidade.