Grafo de Hoffman-Singleton

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Hoffman–Singleton
Hoffman-Singleton graph.svg
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[editar | editar código-fonte]

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 | editar código-fonte]

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)^{21}. Portanto o grafo de Hoffman-Singleton é um grafo integral: seu espectro de grafo consiste inteiramente de inteiros.

Referências

  1. a b Eric W. Weisstein, Hoffman-Singleton Graph em MathWorld
  2. Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
  3. Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. 28 de Setembro de 2004. [1]
  4. Brouwer, Andries E., Hoffman-Singleton graph, http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html .
  5. Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf .