Loading AI tools
Da Wikipédia, a enciclopédia livre
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]
Na notação de Watkins, G(n,k) é um grafo com conjunto de vértices
e conjunto de arestas
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}.
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).
Esta família de grafos possui um número de propriedades interessantes. Por exemplo,
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.