Jarl af Heawood

Heawood-grafen  er en urettet graf med 14 spidser og 21 kanter, opkaldt efter Percy John Heawood [1] .

Kombinatoriske egenskaber

Grafen er kubisk , og alle cyklusser i grafen indeholder seks eller flere kanter. Enhver mindre kubisk graf indeholder mindre cyklusser, så denne graf er en (3,6) -celle , den mindste kubiske graf med omkreds 6. Den er også afstandstransitiv (se Fosters liste ), og derfor afstandsregulær [2] . Der er 24 matchninger i Heawood-grafen , og i alle matchninger danner de kanter, der ikke er inkluderet i matchningen, en Hamiltonsk cyklus . For eksempel viser figuren grafens toppunkter placeret på en cirkel og danner en cyklus, og diagonalerne inde i cirklen danner en match. Hvis vi deler kanterne af cyklussen i to matchninger, får vi tre perfekte matchninger (det vil sige en 3-farvet farvning af kanterne ) på otte forskellige måder [2] . På grund af grafens symmetri kan to perfekte matchninger og to Hamiltonske cyklusser transformeres fra den ene til den anden [3] .

Heawood-grafen har 28 cyklusser, der hver indeholder seks hjørner. Hver sådan cyklus er ikke nøjagtigt relateret til de andre tre 6-vertex-cyklusser. Blandt disse tre cyklusser er hver den symmetriske forskel på de to andre. En graf, hvor hvert toppunkt svarer til en cyklus på 6 hjørner i Heawood-grafen, og buerne svarer til afbrudte par, er Coxeter-grafen [4] .

Geometriske og topologiske egenskaber

Heawood-grafen er en ringformet graf , hvilket betyder, at den kan indlejres uden skæringspunkter i en torus . En sådan type indlejring placerer hjørnerne og kanterne af en graf i det tredimensionelle euklidiske rum som et sæt af hjørner og kanter af en ikke-konveks polytop med torustopologi, Silashi-polytopen . Grafen er opkaldt efter Percy John Heawood , som beviste i 1890, at syv farver er tilstrækkelige til at farve enhver torus polygon flisebelægning [5] [6] . Heawood-grafen danner en opdeling af torus i syv indbyrdes tilstødende områder, hvilket viser, at grænsen er nøjagtig. Heawood-grafen er også Levi-grafen for Fano-planet , det vil sige grafen, der repræsenterer forekomsten af ​​punkter og linjer i denne geometri. I denne fortolkning svarer cyklusserne med længde 6 i Heawood-grafen til trekanter på Fano-overfladen. Heawood-grafen har et krydsningstal på 3 og er den mindste kubiske graf med dette antal krydsninger [7] . Sammen med Heawood-grafen er der 8 forskellige grafer af størrelsesorden 14 med et antal krydsninger på 3. Heawood-grafen er en enhedsafstandsgraf  - den kan indlejres i et plan, så tilstødende hjørner er præcis i en afstand af én, mens der ikke vil falde to hjørner på det samme sted i flyet, og intet punkt vil være inden for kanten. Kendte indlejringer af denne type mangler dog den iboende symmetri i en graf [8] .

Algebraiske egenskaber

Automorfigruppen i Heawood- grafen er isomorf med den projektive lineære gruppe PGL 2 (7), en gruppe af orden 336 [9] . Den virker transitivt på grafens spidser, kanter og buer, så Heawood-grafen er symmetrisk . Der er automorfier, der tager et hvilket som helst toppunkt til et hvilket som helst andet toppunkt og enhver kant til enhver anden kant. Ifølge Fosters liste er Heawood-grafen, betegnet F014A, den eneste kubiske graf med 14 hjørner [10] [11] . Det karakteristiske polynomium i Heawood -grafmatricen er . Grafens spektrum er Dette er den eneste graf med et sådant polynomium, der er bestemt af spektret.

Grafens kromatiske polynomium er:

Galleri

• Silashi-polyederet .

• Heawood-grafen har 3 krydsninger .

• Det kromatiske indeks for Heawood-grafen er 3.

• Det kromatiske tal på Heawood-grafen er 2.

• En indlejring af Heawood-grafen i en torus (vist som en firkant med periodiske grænsebetingelser ), der deler den i syv indbyrdes tilstødende områder

Noter

1. ↑ Weisstein, Eric W. Heawood Graph  på Wolfram MathWorld -webstedet .
2. ↑ 1 2 Brouwer, Andries E. Heawood graf . Tilføjelser og rettelser til bogen "Distance-Regular Graphs" (Brouwer, Cohen, Neumaier; Springer; 1989) . Hentet 2. januar 2014. Arkiveret fra originalen 1. august 2012. (ubestemt)
3. ↑ M. Abreu, REL Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Grafer og digrafer med alle 2-faktorer isomorfe // Journal of Combinatorial Theory. - 2004. - T. 92 , no. 2 . - S. 395-404 . - doi : 10.1016/j.jctb.2004.09.004 . .
4. ↑ Italo J. Dejter. Fra Coxeter-grafen til Klein-grafen // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
5. ↑ Ezra Brown. De mange navne på (7,3,1) // Mathematics Magazine . - 2002. - T. 75 , no. 2 . - S. 83-94 . - doi : 10.2307/3219140 . — .
6. ↑ PJ Heawood. Kortfarvesætninger // Quarterly J. Math. Oxford Ser. - 1890. - T. 24 . - S. 322-339 .
7. ↑ OEIS -sekvens A110507 _
8. ↑ Eberhard H., A. Gerbracht. Elleve enhedsafstandsindlejringer af Heawood-grafen. - 2009. - arXiv : 0912.5395 . .
9. ↑ JA Bondy, USR Murty. Grafteori med applikationer . - New York: Nordholland, 1976. - S. 237. - ISBN 0-444-19451-7 .
10. ↑ Royle, G. "Kubiske symmetriske grafer (Foster's liste)." Arkiveret fra originalen den 20. juli 2008.
11. ↑ Marston Conder og Dobcsányi, P. "Trivalente symmetriske grafer op til 768 hjørner." J. Combin. Matematik. Forene. Comput. 40, 41-63, 2002.