![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/fc/Foster_graph.svg/langpt-640px-Foster_graph.svg.png&w=640&q=50)
Grafo de Foster
De Wikipedia, a enciclopédia encyclopedia
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]
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 |
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.