Biggs-Smithov graf

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-točkovno-povezan in 3-povezavno-povezan.

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

Algebrske značilnosti

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.

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

Karakteristični polinom Biggs-Smithovega grafa je:

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

Upodobitve

• 
  Kromatično število Biggs-Smithovega grafa je 3.
• 
  Kromatični indeks Biggs-Smithovega grafa je 3.
• 
  Alternativna upodobitev Biggs-Smithovega grafa.
• 
  Dekompozicija Biggs-Smithovega grafa v 6 množic z velikostjo 17.

Viri

• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat

Zunanje povezave

• Predloga:MathWorld