Grafo de Hoffman–Singleton | |
---|---|
![]() | |
Nomeado em honra a | Alan J. Hoffman Robert R. Singleton |
vértices | 50 |
arestas | 175 |
Raio | 2 |
Diâmetro | 2[1] |
Cintura | 5[1] |
Automorfismos | 252000 (PGL(3,52):2)[2] |
Número cromático | 4 |
Índice cromático | 7[3] |
Propriedades | Simétrico Grafo de Moore Hamiltoniano Integral Gaiola Fortemente regular |
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).[4] 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.[5] Como é um grafo de Moore onde cada vértice tem grau 7, e sua cintura é 5, ele é um (7,5)-gaiola.
Uma construção simples, direta é como se segue: Tome cinco pentágonos Ph e cinco pentagramas Qi, de forma que o vértice j de Ph seja adjacente aos vértices j-1,j+1 de Ph e o vértice j de Qi seja adjacente aos vértices j-2,j+2 de Qi. Agora conecte o vértice j de Ph ao vértice hi+j de Qi. (Todos os índices mod 5.)
O grupo de automorfismo do grafo de Hoffman-Singleton é um grupo de ordem 252000 isomórfico a PΣU(3,52). 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 . Portanto o grafo de Hoffman-Singleton é um grafo integral: seu espectro de grafo consiste inteiramente de inteiros.