Grafo de Foster
Grafo de Foster | |
---|---|
Nomeado em honra a | Ronald Martin Foster |
vértices | 90 |
arestas | 135 |
Raio | 8 |
Diâmetro | 8 |
Cintura | 10 |
Automorfismos | 4320 |
Número cromático | 2 |
Índice cromático | 3 |
Propriedades | Cúbico simétrico distância-transitivo Hamiltoniano simétrico |
No campo da matemática da teoria dos grafos, o Grafo de Foster é um grafo 3-regular com 90 vértices e 135 arestas.[1]
O grafo de Foster é Hamiltoniano e tem número cromático 2, índice cromático 3, raio 8, diâmetro 8 e cintura 10. Ele é também um grafo 3-vértice-conectado e 3-aresta-conectado.
Todos os grafos distância-regular cúbicos são conhecidos.[2] O grafo de Foster é um destes 13 grafos. É o único grafo distância-transitivo com array de intersecção {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}.[3] Pode ser construído como o grafo de incidência do espaço parcial linear, que é a única cobertura tripla com nenhum 8-gono do quadrângulo generalizado GQ(2,2). É nomeado em honra a R. M. Foster, cujo censo de Foster de grafos simétricos cúbicos incluíam este grafo.
Propriedades algébricas
O grupo de automorfismo do grafo de Foster é um grupo de ordem 4320.[4] Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto o grafo de Foster é um grafo simétrico. Ele tem automorfismos que levam qualquer vértice para qualquer outro vértice e qualquer aresta a qualquer outra aresta. Segundo o censo de Foster, o grafo de Foster, referenciado como F90A, é o único grafo cúbico simétrico em 90 vértices.[5]
O polinômio característico do grafo de Foster é igual a .
Galeria
- Grafo de Foster colorido para ressaltar vários ciclos.
- O número cromático do grafo de Foster é 2.
- O índice cromático do grafo de Foster é 3.
Referências
- ↑ Weisstein, Eric W. «Foster Graph». MathWorld (em inglês)
- ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ↑ Cubic distance-regular graphs, A. Brouwer.
- ↑ Royle, G. F090A data[ligação inativa]
- ↑ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002