Grafo de Hoffman-Singleton

Grafo de Hoffman–Singleton
Nomeado em honra a	Alan J. Hoffman Robert R. Singleton
vértices	50
arestas	175
Raio	2
Diâmetro	2
Cintura	5
Automorfismos	252000 (PGL(3,52):2)
Número cromático	4
Índice cromático	7
Propriedades	Simétrico Grafo de Moore Hamiltoniano Integral Gaiola Fortemente regular

O grafo de Hoffman-Singleton. O subgrafo das arestas azuis é a soma dos dez pentágonos disjuntos.

No campo da matemática da teoria dos grafos, o Grafo de Hoffman–Singleton é um grafo 7-regular não direcionado com 50 vértices e 175 arestas. É o único grafo fortemente regular com parâmetros (50,7,0,1). Foi construído por Alan Hoffman e Robert Singleton ao tentar classificar todos os grafos de Moore, e é a mais alta ordem de grafo de Moore esistente conhecida até o momento. Como é um grafo de Moore onde cada vértice tem grau 7, e sua cintura é 5, ele é um (7,5)-gaiola.

Construção

Uma construção simples, direta é como se segue: Tome cinco pentágonos P_h e cinco pentagramas Q_i, de forma que o vértice j de P_h seja adjacente aos vértices j-1,j+1 de P_h e o vértice j de Q_i seja adjacente aos vértices j-2,j+2 de Q_i. Agora conecte o vértice j de P_h ao vértice hi+j de Q_i. (Todos os índices mod 5.)

Propriedades algébricas

O grupo de automorfismo do grafo de Hoffman-Singleton é um grupo de ordem 252000 isomórfico a PΣU(3,5²). Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto, o grafo de Biggs–Smith é im grafo simétrico.

O polinômio característico do grafo de Hoffman-Singleton é igual a $(x-7) (x-2)^{28} (x+3)^{21}$. Portanto o grafo de Hoffman-Singleton é um grafo integral: seu espectro de grafo consiste inteiramente de inteiros.