Hoffman-Singletonov graf

Hoffman-Singletonov graf
Ime	Alan Jerome Hoffman Robert R. Singleton
Točke	50
Povezave	175
Polmer	2
Premer	2
Notranji obseg	5
Avtomorfizem	252.000 (PSU(3,52):2)
Kromatično število	4
Kromatični indeks	7
Značilnosti	krepko regularen simetričen Hamiltonov celoštevilčen kletka Mooreov

Hoffman-Singletonov graf. Podgraf z modrimi povezavami je vsota desetih petkotnikov.

Hoffman-Singletonov graf je v teoriji grafov 7-regularni neusmerjeni graf s 50 točkami in 175 povezavami. Je edini krepko povezani graf s parametri (50,7,0,1). Skonstruirala sta ga Alan Jerome Hoffman in Robert R. Singleton pri klasifikaciji vseh Mooreovih grafov. Hoffman-Singletonov graf je Mooreov graf z največjim znanim redom. Ker je Mooreov graf v katerem ima vsaka točka stopnjo 7, njegov notranji obseg pa je 5, je tudi (7,5)-kletka.

Konstrukcija

Preprosta neposredna konstrukcija je naslednja: vzemi pet petkotnikov P_h in pet pentagramov Q_i, tako da je točka j iz P_h sosednja točkam j-1,j+1 v P_h, točka j iz Q_i pa je sosednja točkam j-2,j+2 v Q_i. Nato poveži točko j iz P_h s točko hi+j iz Q_i. (Vsi indeksi mod 5.)

Algebrske značilnosti

Grupa avtomorfizmov Hoffman-Singletonovega grafa je grupa reda 252.000 izomorfna PΣU(3,5²), poldirektnemu produktu projektivni posebni unitarni grupi PSU(3,5²) s ciklično grupo reda 2, tvorjeno s Frobeniusovim avtomorfizmom. Hoffman-Singletonov graf je točkovno in razdaljno-prehoden, ter zato simetričen.

Karakteristični polinom Hoffman-Singletonovega grafa je:

$(x-7) (x-2)^{28} (x+3)^{21} \!\, .$

Hoffman-Singletonov graf je zaradi tega celoštevilčni graf: njegov spekter v celoti sestavljajo le cela števila.

Viri

• Benson, C. T.; Losey, N. E. (1971). "On a graph of Hoffman and Singleton". Journal of Combinatorial Theory. Series B 11: 67–79. doi:10.1016/0095-8956(71)90015-3. MR0281658. ISSN 0095-8956. 

• Brouwer, Andries Evert. Hoffman-Singleton graph (v angleščini).

• Hafner, P. R. (2003). "The Hoffman-Singleton Graph and Its Automorphisms". J. Algebraic Combin. 18: 7-12. 

• Hoffman, Alan Jerome; 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. 

• Holton, D. A.; Sheehan,J. (1993). The Petersen graph. Cambridge University Press. Str. 186 in 190. ISBN 0-521-43594-3. 

• Royle, G. (2004-09-28). Re: What is the Edge Chromatic Number of Hoffman-Singleton? (v angleščini). GRAPHNET@istserv.nodak.edu posting..

Zunanje povezave

• Hoffman-Singleton Graph na MathWorld (v angleščini)