Biggs-Smithov graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Biggs-Smithov graf
Biggs-Smith graph.svg
Biggs-Smithov graf
Ime Norman Linstead Biggs
Derek Howard Smith
Točke 102
Povezave 153
Polmer 7
Premer 7
Notranji obseg 9
Avtomorfizem 2448 (PSL(2,17))
Kromatično število 3
Kromatični indeks 3
Značilnosti simetričen
razdaljno-regularen
kubičen
Hamiltonov
Označba F_{102}A\!\,

Biggs-Smithov graf je v teoriji grafov neusmerjeni regularni graf stopnje 3 s 102 točkama in 153 povezavami. Imenuje se po angleških matematikih Normanu Linsteadu Biggsu in Dereku Howardu Smithu.

Njegovo kromatično število je 3, kromatični indeks 3, premer 7, polmer 7 in notranji obseg 9. Biggs-Smithov graf je tudi 3-povezan in 3-povezavno-povezan.

Znani so vsi kubični razdaljno-regularni grafi.[1] Biggs-Smithov graf je dvanajsti od trinajstih takšnih grafov.

Algebrske značilnosti[uredi | uredi kodo]

Grupa avtomorfizmov Biggs-Smithovega grafa je grupa reda 2448, izomorfna projektivni linearni grupi PSL(2,17). Biggs-Smithov graf je točkovno in povezavno-prehoden, ter zato simetričen. Ima avtomorfizme za vsak par točk in povezav. Po Fosterjevem popisu, kjer je označen kot F102A, je edini kubični simetrični graf na 102 točkah.[2]

Biggs-Smithov graf je enolično določen s svojim spektrom, množico lastnih vrednosti svoje matrike sosednosti.[3]

Karakteristični polinom Biggs-Smithovega grafa je:

(x-3) (x-2)^{18} x^{17} (x^{2}-x-4)^{9} (x^{3}+3 x^{2}-3)^{16} \!\, .

Upodobitve[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ Brouwer, Cohen, Neumaier (1989).
  2. ^ Conder, Dobcsányi (2002).
  3. ^ Van Dam, Haemers (2003).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]