Jarl af Coxeter

Coxeter-grafen  er en 3 -regulær graf med 28 hjørner og 42 kanter [1] Alle kubiske afstand-regulære grafer er kendte [2] , Coxeter-grafen er en af ​​13 sådanne grafer.

Egenskaber

Grafens kromatiske tal er 3, det kromatiske indeks er 3, radius er 4, diameteren  er 4, og omkredsen  er 7. Grafen er også 3-vertex-forbundet og 3-kant-forbundet .

Coxeter-grafen er hypo  -Hamiltonsk - den indeholder ikke i sig selv Hamiltonske cyklusser, men fjernelse af ethvert toppunkt gør den Hamiltonsk . Antallet af retlinede krydsninger af Coxeter-grafen er 11, og dette er den mindste kendte kubiske graf med det antal krydsninger, selvom grafer med 26 hjørner og 11 krydsninger kan eksistere [3] .

Coxeter-grafen kan bygges ud fra den noget mindre afstand-regulære Heawood-graf ved at skabe et toppunkt for hver 6-cyklus i Heawood-grafen og en kant for hvert afbrudt par af 6-cyklusser [4] .

Algebraiske egenskaber

Automorfigruppen i en Coxeter-graf er en gruppe af orden 336 [5] . Den virker transitivt på grafens spidser og kanter, så Foster-grafen er symmetrisk . Grafen har automorfier, der kortlægger ethvert toppunkt til en hvilken som helst anden og enhver kant til enhver anden kant. I Fosters liste er Coxeter-grafen, opført som F28A, den eneste kubiske symmetriske graf med 28 hjørner [6] .

Coxeter-grafen er entydigt bestemt af dens spektrum , sættet af egenværdier af grafens tilstødende matrix [7] .

Som en endelig forbundet vertex-transitiv graf, der ikke indeholder nogen Hamilton-cyklus , er Coxeter-grafen et modeksempel på en variant af Lavash-formodningen , men den kanoniske formulering af formodningen kræver tilstedeværelsen af ​​en Hamilton-cyklus.

Kun fem toppunkttransitive grafer uden Hamiltonske cyklusser kendes - den komplette K 2 graf , Petersen grafen, Coxeter grafen og to grafer opnået fra Petersen og Coxeter graferne ved at erstatte hvert toppunkt med en trekant [8] .

Det karakteristiske polynomium i Coxeter-grafen er . Grafen er den eneste graf med et sådant polynomium, hvilket gør grafen unikt defineret af sit spektrum.

Galleri

• Grafen opnået ved at fjerne enhver kant fra Coxeter-grafen er Hamiltonsk forbundet .

• Det kromatiske tal på Coxeter-grafen er 3.

• Antallet af retlinede krydsninger af Coxeter-grafen er 11.

Noter

1. ↑ Weisstein, Eric W. Coxeter Graf  på Wolfram MathWorld- webstedet .
2. ↑ A.E. Brouwer, A.M. Cohen, A. Neumaier. Distance-Regular Graphs. - New York: Springer-Verlag, 1989.
3. ↑ OEIS -sekvens A110507 _
4. ↑ Italo J. Dejter. Fra Coxeter-grafen til Klein-grafen // 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, "Trivalente symmetriske grafer op til 768 hjørner." J. Combin. Matematik. Forene. Comput. 40, 41-63, 2002.
7. ↑ ER van Dam og WH Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, side 189-202, 2003
8. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkiveret fra originalen den 20. juli 2008.