Hoffman-Singletonov graf

Iz Wikipedije, proste enciklopedije
Hoffman-Singletonov graf
ImeAlan Jerome Hoffman
Robert R. Singleton
Točke50
Povezave175
Polmer2
Premer2
Notranji obseg5
Avtomorfizem252.000
(PSU(3,52):2)[1]
Kromatično število4
Kromatični indeks7[2]
Značilnostikrepkoregularen
simetričen
Hamiltonov
celoštevilski
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 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[uredi | uredi kodo]

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

Algebrske značilnosti[uredi | uredi kodo]

Grupa avtomorfizmov Hoffman-Singletonovega grafa je grupa reda 252.000 izomorfna PΣU(3,52), poldirektnemu produktu projektivni posebni unitarni grupi PSU(3,52) 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:

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

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

  • 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?«, GRAPHNET@istserv.nodak.edu posting. (v angleščini)[mrtva povezava]

Zunanje povezave[uredi | uredi kodo]