Goldner – Hararyův graf - Goldner–Harary graph

Goldner – Hararyův graf
Goldner-Harary graph.svg
Pojmenoval podleA. Goldner,
Frank Harary
Vrcholy11
Hrany27
Poloměr2
Průměr2
Obvod3
Automorfismy12 (D6)
Chromatické číslo4
Chromatický index8
VlastnostiPolyhedrální
Rovinný
Chordal
Perfektní
Šířka stromu  3
Tabulka grafů a parametrů

V matematický pole teorie grafů, Goldner – Hararyův graf je jednoduchý neorientovaný graf s 11 vrcholy a 27 hranami. Je pojmenována po A. Goldnerovi a Frank Harary, který v roce 1975 dokázal, že je nejmenší non-Hamiltonian maximální rovinný graf.[1][2][3] Stejný graf již byl uveden jako příklad neholiltonovského zjednodušený mnohostěn podle Branko Grünbaum v roce 1967.[4]

Vlastnosti

Goldner – Hararyův graf je a rovinný graf: lze ho nakreslit v rovině, aniž by se protínal žádný z jeho okrajů. Když je nakreslena v rovině, jsou všechny její plochy trojúhelníkové, což z ní činí a maximální rovinný graf. Stejně jako u každého maximálního rovinného grafu je také 3-vrchol připojený: odstranění jakýchkoli dvou z jeho vrcholů ponechává spojené podgraf.

Goldner – Hararyův graf je také ne-hamiltonovský. Nejmenší možný počet vrcholů pro nehamiltonovský polyedrický graf je 11. Goldner – Hararyův graf je proto minimálním příkladem grafů tohoto typu. Nicméně Herschelův graf, další nehamiltonovský mnohostěn s 11 vrcholy, má méně hran.

Jako nehamiltonovský maximální rovinný graf poskytuje Goldner – Hararyův graf příklad rovinného grafu s tloušťka knihy větší než dva.[5] Na základě existence takových příkladů se Bernhart a Kainen domnívali, že tloušťka knihy rovinných grafů by mohla být libovolně velká, ale následně se ukázalo, že všechny rovinné grafy mají tloušťku knihy maximálně čtyři.[6]

Má to tloušťka knihy 3, chromatické číslo 4, chromatický index 8, obvod 3, poloměr 2, průměr 2 a je 3hranový graf.

Je to také a 3-strom, a proto má šířka stromu 3. Jako každý k-strom, to je chordální graf. Jako rovinný 3-strom tvoří příklad an Apollonian síť.

Geometrie

Podle Steinitzova věta, Goldner – Hararyův graf je a polyedrický graf: je rovinný a 3-spojený, takže existuje konvexní mnohostěn, jehož grafem je Goldner – Harary kostra.

Geometricky může být mnohostěn představující graf Goldner – Harary vytvořen lepením čtyřstěnu na každou stranu trojúhelníkový dipyramid, podobně jako způsob a triakis octahedron je tvořen lepením čtyřstěnu na každou stranu an osmistěn. To znamená, že je Kleetope trojúhelníkového dipyramidu.[4][7] The duální graf grafu Goldner – Harary je geometricky reprezentován symbolem zkrácení z trojúhelníkový hranol.

Algebraické vlastnosti

The automorfická skupina grafu Goldner – Harary je řádu 12 a je izomorfní s dihedrální skupina D6, skupina symetrií a pravidelný šestiúhelník, včetně rotací i odrazů.

The charakteristický polynom grafu Goldner – Harary je: .

Reference

  1. ^ Goldner, A .; Harary, F. (1975), „Poznámka k nejmenšímu nehamiltoniánskému maximálnímu rovinnému grafu“, Býk. Malajská matematika. Soc., 6 (1): 41–42. Viz také stejný deník 6(2): 33 (1975) a 8: 104-106 (1977). Odkaz od seznam Hararyho publikací.
  2. ^ Dillencourt, M. B. (1996), „Mnohostěn malých objednávek a jejich hamiltonovské vlastnosti“, Journal of Combinatorial Theory, Series B, 66: 87–122, doi:10.1006 / jctb.1996.0008.
  3. ^ Přečtěte si, R. C .; Wilson, R. J. (1998), Atlas grafů, Oxford, Anglie: Oxford University Press, s. 285.
  4. ^ A b Grünbaum, Branko (1967), Konvexní Polytopes, Wiley Interscience, s. 357. Stejná stránka, 2. vydání, Graduate Texts in Mathematics 221, Springer-Verlag, 2003, ISBN  978-0-387-40409-7.
  5. ^ Bernhart, Frank R .; Kainen, Paul C. (1979), „Kniha tloušťky grafu“, Journal of Combinatorial Theory, Řada B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2. Viz zejména obrázek 9.
  6. ^ Yannakakis, Mihalis (1986), „Čtyři stránky jsou nezbytné a dostatečné pro rovinné grafy“, Proc. 18. ACM Symp. Theory of Computing (STOC), str. 104–108, doi:10.1145/12130.12141.
  7. ^ Ewald, Günter (1973), „Hamiltonovské obvody v zjednodušených komplexech“, Geometriae Dedicata, 2 (1): 115–125, doi:10.1007 / BF00149287.

externí odkazy