Grafo de Petersen generalizado

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
O grafo de Dürer G(6,2).

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[1] e estes grafos receberam seu nome em 1969 por Mark Watkins.[2]

Definição e notação[editar | editar código-fonte]

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

{u0, u1, ..., un−1, v0, v1, ..., vn−1}

e conjunto de arestas

{ui ui+1, ui vi, vi vi+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[3] Exemplo 2.1.2, p. 58.

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

Exemplos[editar | editar código-fonte]

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[editar | editar código-fonte]

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).[4] 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.[5]

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

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

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

Referências

  1. COXETER, H. S. M.. (1950). "Self-dual configurations and regular graphs". Bulletin of the American Mathematical Society 56: 413–455. DOI:10.1090/S0002-9904-1950-09407-5..
  2. WATKINS, Mark E.. (1969). "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs". Journal of Combinatorial Theory 6: 152–164. DOI:10.1016/S0021-9800(69)80116-X..
  3. GROSS, Jonathan L.; TUCKER, Thomas W.. Topological Graph Theory. New York: Wiley, 1987. .
  4. FRUCHT, R.; GRAVER, J. E.; WATKINS, M. E.. (1971). "The groups of the generalized Petersen graphs". Proceedings of the Cambridge Philosophical Society 70: 211–218. DOI:10.1017/S0305004100049811..
  5. ALSPACH, B. R.. (1983). "The classification of Hamiltonian generalized Petersen graphs". Journal of Combinatorial Theory, Series B 34: 293–312. DOI:10.1016/0095-8956(83)90042-4..
  6. THOMASON, Andrew. (1982). "Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable". Journal of Graph Theory 6 (2): 219–221. DOI:10.1002/jgt.3190060218..
  7. CASTAGNA, Frank; PRINS, Geert. (1972). "Every Generalized Petersen Graph has a Tait Coloring". Pacific Journal of Mathematics 40..
  8. ŽITNIK, Arjana; HORVAT, Boris; PISANSKI, Tomaž (2010). All generalized Petersen graphs are unit-distance graphs..