Goldner gróf – Harari

A gráfelméletben a Goldner-Harari gráf  egy egyszerű irányítatlan gráf , 11 csúcsával és 27 élével. A fájl A. Goldner és F. Harari nevéhez fűződik , akik 1975-ben bebizonyították, hogy ez a legkisebb nem Hamilton-féle maximális síkgráf [1] [2] [3] . Ugyanezt a gráfot Grünbaum már 1967 - ben megadta példaként egy nem-hamiltoni egyszerűsített politópra .

Tulajdonságok

A Goldner gráf Harari sík  - síkra rajzolható anélkül, hogy élek kereszteznéd. A síkra rajzolva a gráf minden lapja háromszög alakú, így egy maximális sík gráf . Mint minden maximális síkgráf, ez is 3 csúcsú  - ha két csúcsot eltávolítunk, a részgráf összekapcsolva marad.

Goldner grófja a nem hamiltoniak hararija . A nem Hamilton-féle poliéder gráfok csúcsainak lehető legkisebb száma 11. Így a Goldner-Harari gráf egy példa egy ilyen típusú minimális gráfra. Azonban a Herschel-gráfnak , egy másik nem Hamilton-féle poliédernek 11 csúcsa van, kevesebb éllel rendelkezik.

Maximális síkbeli nem-hamiltoni gráfként a Goldner-Harari gráf példát ad kettőnél nagyobb könyvvastagságú síkgráfra [5] . Ilyen példák megléte alapján Bernhart és Kainen (Bernhart, Kainen) azt sejtették, hogy a síkgráfok könyvvastagsága tetszőlegesen nagy lehet, de aztán kiderült, hogy minden síkgráf könyvvastagsága nem haladja meg a négyet [6] .

A gráf könyvvastagsága 3, kromatikus száma 4, kromatikus indexe 8, kerülete 3, sugara 2, átmérője 2, a gráf 3 élkapcsolatú .

A gráf is 3-fa , tehát a faszélessége 3. Mint minden k - fa, a gráf is akkordális . Síkbeli 3-faként a gráf egy Apollonius-hálózat példáját mutatja be .

Geometria

Steinitz tétele szerint a Goldner-Harari gráf poliéder gráf  - síkbeli és 3-összefüggésben van, tehát van egy konvex poliéder, amelynek a Goldner-Harari gráf a váza .

Geometriailag a Goldner-Harari gráf poliéderes ábrázolása úgy alakítható ki, hogy egy tetraédert ragasztunk egy háromszög alakú bipiramis minden lapjára , ugyanúgy, ahogy egy triakisztetraédert úgy alakítunk ki, hogy az oktaéder minden lapjára egy tetraédert ragasztunk . Azaz egy háromszög alakú dipiramis Klee poliédere [4] [7] . Goldner-Harari gróf duális gráfját geometriailag egy háromszög prizma csonkolásával ábrázoljuk .

Algebrai tulajdonságok

A Goldner-Harari gráf automorfizmuscsoportja 12-es rendű, és izomorf a D 6 diédercsoporttal , amely egy szabályos hatszög szimmetriacsoportja, amely elforgatásokat és visszaverődéseket is tartalmaz.

A Goldner-Harari gráf karakterisztikus polinomja : .

Jegyzetek

1. ↑ A. Goldner, F. Harary. {{{title}}} // Bull. malajziai matematika. Szoc.. - 1975. - V. 6 , sz. 1 . – S. 41–42 . . Lásd még : 6 (2):33 (1975) és 8 :104-106 (1977). Linkek a Harari publikációinak oldallistájáról Archiválva 2013. január 2-án a Wayback Machine -nél .
2. ↑ M. B. Dillencourt. Kis rendek poliéderei és hamiltoni tulajdonságaik // Journal of Combinatorial Theory, Series B. - 1996. - V. 66 . – S. 87–122 . - doi : 10.1006/jctb.1996.0008 . .
3. ↑ RC Read, RJ Wilson. Grafikonok atlasza. - Oxford, Anglia: Oxford University Press, 1998. - S. 285. .
4. ↑ 1 2 Branko Grünbaum. Konvex politópok. - Wiley Interscience, 1967. - S. 357. .
5. ↑ Frank R. Bernhart, Paul C. Kainen. Egy gráf könyv vastagsága. - Journal of Combinatorial Theory, B. sorozat - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
6. ↑ Mihalis Yanakakis. Proc. 18. ACM Symp. A számítástechnika elmélete (STOC). - 1986. - S. 104-108. - doi : 10.1145/12130.12141 . .
7. ↑ Gunter Ewald. Hamilton áramkörök egyszerű komplexekben // Geometriae Dedicata. - 1973. - 2. kötet , szám. 1 . – S. 115–125 . - doi : 10.1007/BF00149287 . .

Linkek

• Weisstein, Eric W. Goldner-Harary grafikon  (angol) a Wolfram MathWorld webhelyen .