Grafo de Holt
Predefinição:Info/Grafo No campo da matemática da teoria dos grafos o grafo de Holt ou grafo de Doyle é o menor grafo meio-transitivo, ou seja, o menor exemplo de grafo vértice-transitivo e aresta-transitivo que não é também simétrico.[1][2] Esses grafos não são comuns.[3] É nomeado em honra a Peter G. Doyle e Derek F. Holt, que descobriram o mesmo grafo de forma independente em 1976[4] e 1981[5] respectivamente.
O grafo de Holt tem um diâmetro de 3, raio 3, cintura 5, número cromático 3, índice cromático 5 e é hamiltoniano com 98472 ciclos distintos hamiltonianos.[6] é também um grafo 4-vértice-conectado e 4-aresta-conectado.
Ele tem um grupo de automorfismo da ordem de 54 automorfismos.[6] Este é um grupo menor que um grafo simétrico com o mesmo número de vértices e arestas teria. O desenho do grafo à direita destaca isto, na medida em que carece de simetria reflexiva.
O polinômio característico do grafo de Holt é:
Galeria
-
O número cromático do grafo de Holt é 3. -
O índice cromático do grafo de Holt é 5. -
O grafo de Holt é Hamiltoniano.
- ↑ Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1]
- ↑ Predefinição:Citar jornal.
- ↑ Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, ISBN 1584880902, p. 491.
- ↑ Predefinição:Citation. Como citado pela MathWorld.
- ↑ Predefinição:Citar jornal.
- ↑ 6,0 6,1 Predefinição:MathWorld