Grafo de Hoffman-Singleton Construção | Propriedades algébricas | Referências Menu de navegação«Hoffman-Singleton Graph»Hoffman-Singleton graph«Moore graphs with diameter 2 and 3»0140437
Grafos regularesGrafos individuais
matemáticateoria dos grafosgrafo 7-regulargrafo fortemente regulargrafos de Mooregrafo de Mooregraucinturagaiolagrupo de automorfismografo simétricopolinômio característicografo integralespectro de grafo
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 |
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).[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.
Construção |
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 |
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 (x−7)(x−2)28(x+3)21displaystyle (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.
Referências
↑ ab 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 .
