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.

Biggs-Smithov graf
Biggs-Smithov graf
ImeNorman Linstead Biggs
Derek Howard Smith
Točke102
Povezave153
Polmer7
Premer7
Notranji obseg9
Avtomorfizem2448 (PSL(2,17))
Kromatično število3
Kromatični indeks3
Značilnostisimetričen
razdaljno-regularen
kubičen
Hamiltonov
Označba

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.[1] Biggs-Smithov graf je dvanajsti od trinajstih takšnih grafov.

Algebrske značilnosti

uredi

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:

 

Upodobitve

uredi

Sklici

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

uredi