Earl of Coxeter

Coxeterin graafi  on 3- säännöllinen graafi , jossa on 28 kärkeä ja 42 reunaa [1] Kaikki kuutioetäisyyssäännölliset graafit tunnetaan [2] , Coxeterin graafi on yksi 13 sellaisesta graafista.

Ominaisuudet

Graafin kromaattinen luku on 3, kromaattinen indeksi 3, säde 4, halkaisija  4 ja ympärysmitta  7. Graafi on myös 3-vertex- ja 3-edge-connected .

Coxeterin graafi on hypo  -Hamiltonin - se ei itsessään sisällä Hamiltonin jaksoja, mutta minkä tahansa kärjen poistaminen tekee siitä Hamiltonin . Coxeter-graafin suoraviivaisten risteysten lukumäärä on 11, ja tämä on pienin tunnettu kuutiograafi tällä risteysmäärällä, vaikka graafisia 26 kärkeä ja 11 risteystä voi olla olemassa [3] .

Coxeter-graafi voidaan rakentaa hieman pienemmän etäisyyden säännöllisestä Heawood-graafista luomalla kullekin Heawood-graafin 6-syklille kärkipiste ja kullekin irtikytketylle 6-syklin parille reuna [4] .

Algebralliset ominaisuudet

Coxeterin graafin automorfismiryhmä on luokkaa 336 oleva ryhmä [5] . Se vaikuttaa transitiivisesti graafin kärkipisteisiin ja reunoihin, joten Foster-graafi on symmetrinen . Graafilla on automorfismeja, jotka kuvaavat minkä tahansa kärjen mihin tahansa toiseen ja minkä tahansa reunan mihin tahansa muuhun reunaan. Fosterin luettelossa Coxeterin graafi, joka on listattu nimellä F28A, on ainoa kuutiosymmetrinen graafi, jossa on 28 kärkeä [6] .

Coxeter-graafin määrittää yksiselitteisesti sen spektri , graafin vierekkäisyysmatriisin ominaisarvot [7] .

Coxeterin graafi on äärellisenä yhdistettynä kärkitransitiivisenä graafina, joka ei sisällä Hamiltonin sykliä , vastaesimerkki Lavashin arvelun muunnelmasta , mutta oletuksen kanoninen muotoilu edellyttää Hamiltonin syklin läsnäoloa.

Tunnetaan vain viisi kärkitransitiivistä graafia ilman Hamiltonin sykliä - täydellinen K 2 -graafi , Petersen- graafi, Coxeterin graafi sekä kaksi graafia, jotka on saatu Petersenin ja Coxeterin graafista korvaamalla kukin kärki kolmiolla [8] .

Coxeterin graafin ominaispolynomi on . Graafi on ainoa graafi, jossa on tällainen polynomi, mikä tekee graafista yksilöllisen spektrin määrittelemän.

Galleria

• Graafi, joka saadaan poistamalla mikä tahansa reuna Coxeterin graafista, on Hamiltonin yhdistetty .

• Coxeterin graafin kromaattinen luku on 3.

• Coxeter-graafin suoraviivaisten risteysten määrä on 11.

Muistiinpanot

1. ↑ Weisstein, Eric W. Coxeter Graph  Wolfram MathWorld -verkkosivustolla .
2. ↑ A.E. Brouwer, A.M. Cohen, A. Neumaier. Etäisyys-säännölliset kaaviot - New York: Springer-Verlag, 1989.
3. ↑ OEIS - sekvenssi A110507 _
4. ↑ Italo J. Dejter. Coxeterin graafista Kleinin graafiin // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
5. ↑ Royle, G. F028A data  (downlink)
6. ↑ M. Conder, P. Dobcsányi, "Trivalent Symmetric Graphs Jopa 768 Vertices." J. Combin. Matematiikka. Yhdistää. Comput. 40, 41-63, 2002.
7. ↑ ER van Dam ja WH Haemers, Joidenkin etäisyyssäännöllisten kuvaajien spektraaliset karakterisoinnit. J. Algebraic Combin. 15, sivut 189-202, 2003
8. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkistoitu alkuperäisestä 20. heinäkuuta 2008.