Hrabě z Biggs-Smith

Biggs-Smithův graf  je 3- regulární graf se 102 vrcholy a 153 hranami [1] . Pojmenováno po Biggsovia Smith, který popsal graf v roce 1971. [2]

Barevné číslo grafu je 3, chromatický index je 3, poloměr je 7, průměr je 7 a obvod je 9. Graf je také spojen 3 vrcholy a 3 hranami .

Všechny kubické vzdálenosti-regulární grafy jsou známy [3] , Biggs-Smithův graf je jedním ze 13 takových grafů.

Algebraické vlastnosti

Grupa automorfismu Biggs-Smithova grafu je grupa řádu 2448 [4] izomorfní k projektivní grupě PSL(2,17). Působí tranzitivně na vrcholy a hrany grafu, takže Biggs-Smithův graf je symetrický . Graf má automorfismy, které mapují jakýkoli vrchol na jakýkoli jiný a jakoukoli hranu na jakoukoli jinou hranu. Ve Fosterově seznamu je Biggs-Smithův graf, uvedený jako F102A, jediným symetrickým grafem se 102 vrcholy [5] .

Biggs-Smithův graf je jednoznačně určen svým spektrem , množinou vlastních hodnot matice sousednosti grafu [6] .

Charakteristický polynom Biggs-Smithova grafu je:

Galerie

• Barevné číslo Count Biggs-Smith je 3.

• Chromatický index Biggs-Smithova grafu je 3.

• Alternativní grafické znázornění hraběte Biggs-Smitha.

• Rozklad Biggs-Smithova grafu na 6 sad po 17 prvcích.

Poznámky

1. ↑ Weisstein, Eric W. Biggs–Smith Graph  na webu Wolfram MathWorld .
2. ↑ Biggs, NL, & Smith, D. H. (1971). Na trivalentních grafech. Bulletin of the London Mathematical Society, 3(2), 155–158. doi:10.1112/blms/3.2.155
3. ↑ A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs. - New York: Springer-Verlag, 1989.
4. ↑ Royle, G. Data F102A  (downlink)
5. ↑ M. Conder, P. Dobcsányi, "Trivalentní symetrické grafy až do 768 vrcholů." J. Combin. Matematika. Kombajn. Počítat. 40, 41-63, 2002.
6. ↑ ER van Dam a WH Haemers, Spektrální charakterizace některých vzdálenostně-regulárních grafů. J. Algebraická kombinace. 15, strany 189-202, 2003

Literatura

• O trivalentních grafech, NL Biggs, D. H. Smith - Bulletin of the London Mathematical Society, 3 (1971) 155-158.