Hoffman-Singletonov graf

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). 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: 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:

$(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.

Viri

• Predloga:Citat
• Predloga:Navedi splet
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:CitatPredloga:Slepa povezava

Zunanje povezave

• Predloga:MathWorld