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.

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. 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}. 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. 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.

O polinômio característico do grafo de Foster é igual a $(x-3)(x-2)^{9}(x-1)^{18}x^{10}(x+1)^{18}(x+2)^{9}(x+3)(x^{2}-6)^{12}$.

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.