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

• 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

• Weisstein, Eric Wolfgang. »Biggs-Smith Graph«. MathWorld.