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,5^2):2)[1]
Kromatično število	4
Kromatični indeks	7[2]
Značilnosti	krepkoregularen simetričen Hamiltonov celoštevilski kletka Mooreov
p p u

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 krepkopovezani graf s parametri (50,7,0,1).^[3] 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.^[4] 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: vzame se 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 se poveže 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 razdaljnoprehoden, ter zato simetričen.

Karakteristični polinom Hoffman-Singletonovega grafa je:

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

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

Sklici

1. Hafner (2003).
2. Royle (2004).
3. Brouwer.
4. Hoffman; Singleton (1960).

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, ISSN 0095-8956, MR 0281658
• 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« (PDF), IBM Journal of Research and Development, 5 (4): 497–504, MR 0140437
• Holton, D. A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, str. 186 in 190, ISBN 0-521-43594-3
• Royle, G. (28. september 2004), »Re: What is the Edge Chromatic Number of Hoffman-Singleton?«, [e-mail] posting. (v angleščini)^{[mrtva povezava]}

Zunanje povezave

• Weisstein, Eric Wolfgang. »Hoffman-Singleton Graph«. MathWorld.