Hrabě z Heawood

Heawoodův graf  je neorientovaný graf se 14 vrcholy a 21 hranami, pojmenovaný po Percy Johnu Heawoodovi [1] .

Kombinatorické vlastnosti

Graf je kubický a všechny cykly v grafu obsahují šest nebo více hran. Každý menší kubický graf obsahuje menší cykly, takže tento graf je (3,6) -cell , nejmenší kubický graf s obvodem 6. Je také vzdálenostně tranzitivní (viz Fosterův seznam ), a tedy vzdálenostně regulární [2] . V Heawoodově grafu je 24 shod a ve všech shodách tvoří hrany, které nejsou zahrnuty ve shodě, hamiltonovský cyklus . Obrázek například ukazuje vrcholy grafu umístěné na kružnici a tvořící cyklus a úhlopříčky uvnitř kruhu tvoří shodu. Pokud rozdělíme hrany cyklu na dvě shody, dostaneme tři dokonalé shody (tedy 3barevné zabarvení hran ) osmi různými způsoby [2] . Díky symetrii grafu lze z jednoho na druhý převést libovolné dvě dokonalé shody a libovolné dva hamiltonovské cykly [3] .

Heawoodův graf má 28 cyklů, z nichž každý obsahuje šest vrcholů. Každý takový cyklus přesně nesouvisí s dalšími třemi cykly se šesti vrcholy. Mezi těmito třemi cykly je každý symetrický rozdíl od ostatních dvou. Graf, ve kterém každý vrchol odpovídá cyklu 6 vrcholů v Heawoodově grafu a oblouky odpovídají rozpojeným párům, je Coxeterův graf [4] .

Geometrické a topologické vlastnosti

Heawoodův graf je toroidní graf , což znamená, že jej lze vložit bez průniků do torusu . Jeden takový typ vkládání umísťuje vrcholy a hrany grafu do trojrozměrného euklidovského prostoru jako množinu vrcholů a hran nekonvexního polytopu s topologií torusu, polytop Silashi . Graf je pojmenován po Percym Johnu Heawoodovi , který v roce 1890 dokázal, že sedm barev stačí k vybarvení jakéhokoli torusového polygonového obkladu [5] [6] . Heawoodův graf tvoří rozdělení torusu do sedmi vzájemně sousedících oblastí, což ukazuje, že hranice je přesná. Heawoodův graf je také Leviho graf Fanovy roviny , tedy graf reprezentující výskyt bodů a čar v této geometrii. V této interpretaci odpovídají cykly délky 6 v Heawoodově grafu trojúhelníkům Fanovy plochy. Heawoodův graf má číslo křížení 3 a je nejmenším kubickým grafem s tímto počtem křížení [7] . Spolu s Heawoodovým grafem existuje 8 různých grafů řádu 14 s počtem křížení 3. Heawoodův graf je jednotkový graf vzdálenosti  - lze jej zasadit do roviny tak, že sousední vrcholy jsou přesně ve vzdálenosti jedné, zatímco žádné dva vrcholy nebudou padat na stejné místo v rovině a žádný bod nebude uvnitř hrany. Známá vložení tohoto typu však postrádá symetrii vlastní grafu [8] .

Algebraické vlastnosti

Grupa automorfismu Heawoodova grafu je izomorfní k projektivní lineární grupě PGL 2 (7), grupa řádu 336 [9] . Působí tranzitivně na vrcholy, hrany a oblouky grafu, takže Heawoodův graf je symetrický . Existují automorfismy, které přenesou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Fosterova seznamu je Heawoodův graf, označený F014A, jediným kubickým grafem se 14 vrcholy [10] [11] . Charakteristickým polynomem matice Heawoodova grafu je . Spektrum grafu je Toto je jediný graf s takovým polynomem, který je určen spektrem.

Chromatický polynom grafu je:

Galerie

• Mnohostěn Silashi .

• Heawoodův graf má 3 křížení .

• Chromatický index Heawoodova grafu je 3.

• Barevné číslo Heawoodova grafu je 2.

• Vložení Heawoodova grafu do torusu (zobrazeného jako čtverec s periodickými okrajovými podmínkami ), jeho rozdělení do sedmi vzájemně sousedících oblastí

Poznámky

1. ↑ Weisstein, Eric W. Heawood Graph  na webu Wolfram MathWorld .
2. ↑ 1 2 Brouwer, Andries E. Heawoodův graf . Dodatky a opravy ke knize "Distance-Regular Graphs" (Brouwer, Cohen, Neumaier; Springer; 1989) . Získáno 2. ledna 2014. Archivováno z originálu 1. srpna 2012. (neurčitý)
3. ↑ M. Abreu, REL Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Grafy a digrafy se všemi 2-faktorovými izomorfními // Journal of Combinatorial Theory. - 2004. - T. 92 , č. 2 . - S. 395-404 . - doi : 10.1016/j.jctb.2004.09.004 . .
4. ↑ Italo J. Dejter. Od Coxeterova grafu po Kleinův graf // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002,1960 . .
5. ↑ Ezra Brown. Mnoho jmen (7,3,1) // Mathematics Magazine . - 2002. - T. 75 , no. 2 . - S. 83-94 . - doi : 10.2307/3219140 . — .
6. ↑ PJ Heawood. Věty o barvení map // Čtvrtletní J. Math. Oxford Ser. - 1890. - T. 24 . - S. 322-339 .
7. ↑ OEIS sekvence A110507 _
8. ↑ Eberhard H., A. Gerbracht. Jedenáct jednotkových vzdáleností vložení Heawoodova grafu. - 2009. - arXiv : 0912.5395 . .
9. ↑ JA Bondy, USR Murty. Teorie grafů s aplikacemi . - New York: North Holland, 1976. - S. 237. - ISBN 0-444-19451-7 .
10. ↑ Royle, G. "Krychlové symetrické grafy (Fosterův seznam)." Archivováno z originálu 20. července 2008.
11. ↑ Marston Conder a Dobcsányi, P. "Trivalentní symetrické grafy až do 768 vrcholů." J. Combin. Matematika. Kombajn. Počítat. 40, 41-63, 2002.