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 | |
---|---|
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 | |
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
urediGrupa 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-
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.
Sklici
urediViri
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