Hrabě Goldner - Harari

V teorii grafů je Goldner-Harariho graf  jednoduchý neorientovaný graf s 11 vrcholy a 27 hranami. Soubor je pojmenován po A. Goldnerovi a F. Hararim , kteří v roce 1975 dokázali, že jde o nejmenší nehamiltonovský maximální planární graf [1] [2] [3] . Stejný graf již uvedl Grünbaum jako příklad nehamiltonovského simpliciálního polytopu v roce 1967. [4]

Vlastnosti

Goldnerův graf je Harariho rovinný  – lze jej kreslit v rovině bez křížení hran. Při kreslení v rovině jsou všechny plochy grafu trojúhelníkové, což z něj činí maximální rovinný graf . Jako každý maximální rovinný graf je také spojen se 3 vrcholy  – odstraněním libovolných dvou vrcholů zůstane podgraf spojený.

Hrabě z Goldneru je Harari z ne-Hamiltonianů . Nejmenší možný počet vrcholů pro nehamiltonovské polyedrické grafy je 11. Příkladem minimálního grafu tohoto typu je tedy Goldner-Harariho graf. Herschelův graf , další nehamiltonovský mnohostěn s 11 vrcholy, má však méně hran.

Jako maximální planární nehamiltonovský graf poskytuje Goldner-Harariho graf příklad rovinného grafu s tloušťkou knihy větší než dvě [5] . Na základě existence takových příkladů se Bernhart a Kainen (Bernhart, Kainen) domnívali, že tloušťka rovinných grafů může být libovolně velká, ale pak se ukázalo, že všechny rovinné grafy mají tloušťku nepřesahující čtyři [6] .

Tloušťka grafu je 3, chromatické číslo je 4, chromatický index je 8, obvod je 3, poloměr je 2, průměr je 2 a graf je spojen se 3 hranami .

Graf je také 3-strom , takže jeho šířka stromu je 3. Jako každý k - strom je graf akordický . Jako planární 3-strom poskytuje graf příklad Apolloniovy sítě .

Geometrie

Podle Steinitzovy věty je Goldner-Harariho graf polyedrický graf  - je rovinný a 3-souvislý, takže existuje konvexní mnohostěn, který má jako kostru Goldner-Harariho graf .

Geometricky lze polyedrickou reprezentaci Goldner-Harariho grafu vytvořit nalepením čtyřstěnu na každou plochu trojúhelníkové bipyramidy stejným způsobem, jako se vytvoří triakistetraedr přilepením čtyřstěnu na každou plochu osmistěnu . Tedy jde o Kleeův mnohostěn trojúhelníkové dipyramidy [4] [7] . Duální graf hraběte Goldnera-Harariho je geometricky reprezentován zkrácením trojúhelníkového hranolu .

Algebraické vlastnosti

Skupina automorfismu Goldner-Harariho grafu má řád 12 a je izomorfní s dihedrální grupou D 6 , grupou symetrie pravidelného šestiúhelníku , která zahrnuje jak rotace, tak odrazy.

Charakteristický polynom Goldner-Harariho grafu je .

Poznámky

1. ↑ A. Goldner, F. Harary. {{{title}}} // Bull. Malajská matematika. Soc.. - 1975. - V. 6 , čís. 1 . — S. 41–42 . . Viz také čísla 6 (2): 33 (1975) a 8 : 104-106 (1977). Odkazy ze seznamu publikací Harariho archivované 2. ledna 2013 na Wayback Machine .
2. ↑ M. B. Dillencourt. Mnohostěny malých řádů a jejich hamiltonovské vlastnosti // Journal of Combinatorial Theory, Series B. - 1996. - V. 66 . — S. 87–122 . - doi : 10.1006/jctb.1996.0008 . .
3. ↑ RC Read, RJ Wilson. Atlas grafů. - Oxford, Anglie: Oxford University Press, 1998. - S. 285. .
4. ↑ 1 2 Branko Grünbaum. Konvexní polytopy. - Wiley Interscience, 1967. - S. 357. .
5. ↑ Frank R. Bernhart, Paul C. Kainen. Tloušťka knihy grafu. - Journal of Combinatorial Theory, řada B. - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
6. ↑ Mihalis Yannakakis. Proč. 18. ACM Symp. Teorie výpočetní techniky (STOC). - 1986. - S. 104-108. - doi : 10.1145/12130.12141 . .
7. ↑ Gunther Ewald. Hamiltonovské okruhy v simpliciálních komplexech // Geometriae Dedicata. - 1973. - Vol. 2 , vydání. 1 . — S. 115–125 . - doi : 10.1007/BF00149287 . .

Odkazy

• Weisstein, Eric W. Goldner-Harary graf  (anglicky) na webových stránkách Wolfram MathWorld .