Hrabě z Coxeter
| hrabě z Coxeter | |
|---|---|
| Vrcholy | 28 |
| žebra | 42 |
| Poloměr | čtyři |
| Průměr | čtyři |
| obvod | 7 |
| Automorfismy | 336 ( PGL 2 (7)) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
kubický
hypohamiltonians |
| Mediální soubory na Wikimedia Commons | |
Coxeterův graf je 3- regulární graf s 28 vrcholy a 42 hranami [1] Všechny kubické vzdálenosti-regulární grafy jsou známé [2] , Coxeterův graf je jedním ze 13 takových grafů.
Vlastnosti
Barevné číslo grafu je 3, chromatický index je 3, poloměr je 4, průměr je 4 a obvod je 7. Graf je také spojen 3 vrcholy a 3 hranami .
Coxeterův graf je hypo -hamiltonovský - sám o sobě neobsahuje hamiltonovské cykly, ale odstraněním libovolného vrcholu se stává hamiltonovským . Počet přímočarých křížení Coxeterova grafu je 11 a toto je nejmenší známý kubický graf s tímto počtem křížení, ačkoli mohou existovat grafy s 26 vrcholy a 11 kříženími [3] .
Coxeterův graf lze sestavit z poněkud menšího Heawoodova grafu s pravidelnou vzdáleností vytvořením vrcholu pro každý 6-cyklus v Heawoodově grafu a hrany pro každý nesouvislý pár 6-cyklů [4] .
Algebraické vlastnosti
Skupina automorfismu Coxeterova grafu je grupa řádu 336 [5] . Působí tranzitivně na vrcholy a hrany grafu, takže Fosterů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 Coxeterův graf, uvedený jako F28A, jediným kubickým symetrickým grafem s 28 vrcholy [6] .
Coxeterův graf je jednoznačně určen svým spektrem , množinou vlastních hodnot matice sousednosti grafu [7] .
Coxeterův graf je jako konečný připojený vrcholově-tranzitivní graf neobsahující žádný hamiltonovský cyklus protipříkladem varianty Lavashovy domněnky , ale kanonická formulace domněnky vyžaduje přítomnost hamiltonovského cyklu.
Je známo pouze pět vertex-tranzitivních grafů bez hamiltonovských cyklů – úplný K 2 graf , Petersenův graf, Coxeterův graf a dva grafy získané z Petersenových a Coxeterových grafů nahrazením každého vrcholu trojúhelníkem [8] .
Charakteristický polynom Coxeterova grafu je . Graf je jediným grafem s takovým polynomem, díky kterému je graf jednoznačně definován svým spektrem.
Galerie
-
Graf získaný odstraněním jakékoli hrany z Coxeterova grafu je Hamiltonově souvislý .
-
Barevné číslo Coxeterova grafu je 3.
-
Počet přímočarých křížení Coxeterova grafu je 11.
Poznámky
- ↑ Weisstein, Eric W. Coxeter Graph na webu Wolfram MathWorld .
- ↑ A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs. - New York: Springer-Verlag, 1989.
- ↑ OEIS sekvence A110507 _
- ↑ Italo J. Dejter. Od Coxeterova grafu po Kleinův graf // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002,1960 . .
- ↑ Royle, G. F028A data (downlink)
- ↑ M. Conder, P. Dobcsányi, "Trivalentní symetrické grafy až do 768 vrcholů." J. Combin. Matematika. Kombajn. Počítat. 40, 41-63, 2002.
- ↑ 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
- ↑ Royle, G. "Krychlové symetrické grafy (The Foster Census)." Archivováno z originálu 20. července 2008.