Grafo de Frucht

No campo da matemática da teoria dos grafos, o Grafo de Frucht é um grafo 3-regular com 12 vértices e 18 arestas e nenhuma simetria não-trivial. Foi descrito pela primeira vez por Robert Frucht em 1939.

Grafo de Frucht
Nomeado em honra a	Robert Frucht
vértices	12
arestas	18
Raio	3
Diâmetro	4
Cintura	3
Automorfismos	1 ({id})
Número cromático	3
Índice cromático	3
Propriedades	Cúbico Planar Hamiltoniano

O grafo de Frucht é um grafo Halin com número cromático 3, índice cromático 3, raio 3, diâmetro 4, e cintura 3. Como em todos os grafos Halin, o grafo de Frucht é planar, 3-vértice-conectado, e poliédrico. É também um grafo 3-aresta-conectado.

O grafo de Frucht é hamiltoniano e pode ser construído a partir da notação LCF: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

Propriedades algébricas

O grafo de Frucht é o menor grafo cúbico possuindo somente um único automorfismo de grafos, a identidade(ou seja, cada vértice pode ser distinguido topologicamente de todos os outros vértices). Tais grafos são chamados assimétricos (ou identidade). O teorema de Frucht diz que qualquer grupo pode ser compreendido como o grupo de simetrias de um grafo, e um reforço deste teorema também devido à Frucht afirma que qualquer grupo pode ser percebido como as simetrias de um grafo 3-regular; o grafo de Frucht fornece um exemplo desta realização para o grupo trivial.

O polinômio característico do grafo de Frucht é igual a $(x-3)(x-2)x(x+1)(x+2)(x^{3}+x^{2}-2x-1)(x^{4}+x^{3}-6x^{2}-5x+4)$.

Galeria

• 
  O grafo de Frucht é planar.
• 
  O número cromático do grafo de Frucht é 3.
• 
  O grafo de Frucht é Hamiltoniano.