Hoffman-Singletonov graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Hoffman-Singletonov graf
Hoffman-Singleton graph.svg
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)[1]
Kromatično število 4
Kromatični indeks 7[2]
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).[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: vzemi 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 poveži 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 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.

Opombe in sklici[uredi | uredi kodo]

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

Viri[uredi | uredi kodo]

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

Zunanje povezave[uredi | uredi kodo]