Coxeter grófja
| Coxeter grófja | |
|---|---|
| Csúcsok | 28 |
| borda | 42 |
| Sugár | négy |
| Átmérő | négy |
| Heveder | 7 |
| Automorfizmusok | 336 ( PGL 2 (7)) |
| Kromatikus szám | 3 |
| Kromatikus index | 3 |
| Tulajdonságok |
köbös
hipohamiltoniak |
| Médiafájlok a Wikimedia Commons oldalon | |
A Coxeter gráf egy 3 - reguláris gráf , 28 csúcsgal és 42 éllel [1] Minden köbtávolság -reguláris gráf ismert [2] , a Coxeter gráf a 13 ilyen gráf egyike.
Tulajdonságok
A gráf kromatikus száma 3, kromatikus indexe 3, sugara 4, átmérője 4, kerülete 7. A gráf 3 csúcs- és 3 élkapcsolatú is .
A Coxeter-gráf hipo -Hamilton-gráf – önmagában nem tartalmaz Hamilton-ciklusokat, de bármely csúcs eltávolítása Hamilton-félevé teszi . A Coxeter-gráf egyenes vonalú keresztezéseinek száma 11, és ez a legkisebb ismert köbös gráf ennyi keresztezéssel, bár létezhetnek 26 csúcsú és 11 keresztezésű gráfok [3] .
A Coxeter-gráf a valamivel kisebb távolságra szabályos Heawood -gráfból építhető fel úgy, hogy a Heawood-gráf minden 6-os ciklusához hozunk létre egy csúcsot, és minden szétválasztott 6-cikluspárhoz egy élt [4] .
Algebrai tulajdonságok
A Coxeter-gráf automorfizmuscsoportja egy 336-os rendű csoport [5] . Tranzitívan hat a gráf csúcsaira és éleire, így a Foster gráf szimmetrikus . A gráfnak vannak olyan automorfizmusai, amelyek bármely csúcsot leképeznek bármely másik élre, és bármely élt bármely másik élre. Foster listáján a Coxeter - gráf, amely F28A-ként szerepel, az egyetlen 28 csúcsú köbös szimmetrikus gráf [6] .
A Coxeter-gráfot egyértelműen a spektruma határozza meg, a gráf szomszédsági mátrixának sajátértékeinek halmaza [7] .
A Coxeter-gráf véges összefüggő csúcstranzitív gráfként, amely nem tartalmaz Hamilton-ciklust , a Lavash-sejtés egy változatának ellenpéldája , de a sejtés kanonikus megfogalmazásához szükség van egy Hamilton-ciklus jelenlétére.
Csak öt csúcstranzitív gráf ismert Hamilton-ciklusok nélkül - a teljes K 2 gráf , a Petersen -gráf, a Coxeter-gráf, valamint két gráf, amelyet a Petersen- és Coxeter-gráfokból kapunk úgy, hogy minden csúcsot háromszöggel helyettesítünk [8] .
A Coxeter-gráf karakterisztikus polinomja : . A gráf az egyetlen gráf ilyen polinommal, amely a gráfot a spektruma alapján egyedileg határozza meg.
Galéria
-
A Coxeter-gráf bármely élének eltávolításával kapott gráf Hamilton-összefüggés .
-
A Coxeter-gráf kromatikus száma 3.
-
A Coxeter-gráf egyenes vonalú keresztezéseinek száma 11.
Jegyzetek
- ↑ Weisstein, Eric W. Coxeter Graph a Wolfram MathWorld webhelyén .
- ↑ A. E. Brouwer, A. M. Cohen, A. Neumaier. Távolság-szabályos grafikonok – New York: Springer-Verlag, 1989.
- ↑ OEIS szekvencia A110507 _
- ↑ Italo J. Dejter. A Coxeter-gráftól a Klein-gráfig // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
- ↑ Royle, G. F028A adatok (lefelé irányuló kapcsolat)
- ↑ M. Conder, P. Dobcsányi, "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Kombájn. Comput. 40, 41-63, 2002.
- ↑ ER van Dam és WH Haemers, Néhány távolság-reguláris gráf spektrális jellemzése. J. Algebrai kombináció. 15., 189-202. oldal, 2003
- ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Az eredetiből archiválva: 2008. július 20.