Grafo de Hoffman-Singleton
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.
| 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 |
Construção editar
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.)
Propriedades algébricas editar
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.
Referências
- ↑ a b Weisstein, Eric W. «Hoffman-Singleton Graph» (em inglês). MathWorld
- ↑ Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
- ↑ Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. 28 de Setembro de 2004. [1]
- ↑ Brouwer, Andries E., Hoffman-Singleton graph.
- ↑ Hoffman, Alan J.; Singleton, Robert R. (1960), «Moore graphs with diameter 2 and 3» (PDF), IBM Journal of Research and Development, 5 (4): 497–504, MR0140437.
