Biggs-Smithov graf

Biggs-Smithov graf
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. 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}+3 x^{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.

Viri

• Biggs, Norman Linstead; Smith, Derek Howard (1971). "On trivalent graphs". Bulletin of the London Mathematical Society 3: 155–158. 
• Brouwer, Andries Evert; Cohen, A. M.; Neumaier, A. (1989). Distance-Regular Graphs. New York: Springer-Verlag. 
• Conder, Marston; Dobcsányi, P. (2002). "Trivalent Symmetric Graphs Up to 768 Vertices". J. Combin. Math. Combin. Comput. 40: 41–63. 
• Van Dam, E. R.; Haemers, W. H. (2003). "Spectral Characterizations of Some Distance-Regular Graphs". J. Algebraic Combin. 15: 189–202. 

Zunanje povezave

• Biggs-Smith Graph na MathWorld (v angleščini)