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 krepkoregularen
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]

Zunanje povezave[uredi | uredi kodo]