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.

Biggs-Smithov graf
Biggs-Smith graph.svg
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čilnostiUredi

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:

 

UpodobitveUredi

SkliciUredi

ViriUredi

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