Biggs – Smithův graf - Biggs–Smith graph

Biggs – Smithův graf
	Biggs – Smithův graf
Vrcholy	102
Hrany	153
Poloměr	7
Průměr	7
Obvod	9
Automorfismy	2448 (PSL (2,17))
Chromatické číslo	3
Chromatický index	3
Vlastnosti	Symetrický; Vzdálenost-pravidelná; Krychlový; Hamiltonian
	Tabulka grafů a parametrů

V matematický pole teorie grafů, Biggs – Smithův graf je 3-běžný graf se 102 vrcholy a 153 hranami.^[1]

Má chromatické číslo 3, chromatický index 3, poloměr 7, průměr 7 a obvod 9. Je to také 3graf spojený s vrcholem a 3-hranový graf.

Všechny krychlový vzdálenost-pravidelné grafy jsou známy.^[2] Biggs – Smithův graf je jedním ze 13 takových grafů.

Algebraické vlastnosti

Skupina automorfismu z Biggs-Smithova grafu je skupina řádu 2448^[3] isomorfní s projektivní speciální lineární skupina PSL (2,17). Působí přechodně na vrcholy, na hrany a na oblouky grafu. Biggs – Smithův graf je tedy a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Biggs – Smithův graf, označovaný jako F102A, je jediný kubický symetrický graf na 102 vrcholech.^[4]

Biggs – Smithův graf je také jednoznačně určen svým grafové spektrum, množina vlastních čísel grafu matice sousedství.^[5]

The charakteristický polynom grafu Biggs – Smith je: ${ displaystyle (x-3) (x-2) ^ {18} x ^ {17} (x ^ {2} -x-4) ^ {9} (x ^ {3} + 3x ^ {2} - 3) ^ {16}}$ .

Galerie

The chromatické číslo grafu Biggs – Smith je 3.
The chromatický index grafu Biggs – Smith je 3.
Alternativní kresba grafu Biggs – Smith.
Rozklad grafu Biggs – Smith na 6 sad velikosti 17.

Reference

^ Weisstein, Eric W. „Biggs – Smithův graf“. MathWorld.
^ Brouwer, A. E.; Cohen, A. M .; a Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
^ Royle, G. Data F102A^{[trvalý mrtvý odkaz ]}
^ Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41–63, 2002.
^ E. R. van Dam a W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraická kombinace. 15, strany 189–202, 2003

Na trojmocných grafech NL Biggs, DH Smith - Bulletin of the London Mathematical Society, 3 (1971) 155-158.

[1] Weisstein, Eric W. „Biggs – Smithův graf“. MathWorld.

[2] Brouwer, A. E.; Cohen, A. M .; a Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.

[3] Royle, G. Data F102A^{[trvalý mrtvý odkaz ]}

[4] Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41–63, 2002.

[5] E. R. van Dam a W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraická kombinace. 15, strany 189–202, 2003

[1]

[2]

[3]

[4]

[5]