Contele Goldner - Harari

În teoria grafurilor, graful Goldner-Harari  este un graf simplu nedirecționat cu 11 vârfuri și 27 de muchii. Fișierul este numit după A. Goldner și F. Harari , care au demonstrat în 1975 că este cel mai mic graf planar maximal non-Hamiltonian [1] [2] [3] . Același grafic a fost deja dat ca exemplu de politop simplonian non-Hamiltonian de către Grünbaum în 1967. [4]

Proprietăți

Graficul Goldner este plan Harari  - poate fi desenat pe un plan fără margini încrucișate. Când sunt desenate pe plan, toate fețele graficului sunt triunghiulare, ceea ce face din acesta un grafic planar maxim . Ca orice graf planar maximal, este, de asemenea , conectat cu 3 vârfuri  - eliminarea oricăror două vârfuri lasă subgraful conectat.

Contele de Goldner este Harari -ul non-Hamiltonienilor . Cel mai mic număr posibil de vârfuri pentru graficele poliedrice non-Hamiltoniene este 11. Astfel, graficul Goldner-Harari este un exemplu de grafic minim de acest tip. Cu toate acestea, Graficul Herschel , un alt poliedru non-Hamiltonian cu 11 vârfuri, are mai puține muchii.

Ca graf planar maximal non-Hamiltonian, graful Goldner-Harari oferă un exemplu de graf plan cu o grosime a cărții mai mare de două [5] . Pe baza existenței unor astfel de exemple, Bernhart și Kainen (Bernhart, Kainen) au presupus că grosimea cărții a grafurilor plane poate fi arbitrar mare, dar apoi s-a demonstrat că toate grafurile plane au o grosime a cărții care nu depășește patru [6] .

Grosimea cărții a graficului este 3, numărul cromatic este 4, indicele cromatic este 8, circumferința este 3, raza este 2, diametrul este 2 și graficul este conectat cu 3 margini .

Graficul este, de asemenea, un arbore cu 3 , deci lățimea arborelui său este de 3. Ca orice arbore k , graficul este cordal . Ca un arbore planar cu trei, graficul oferă un exemplu de rețea Apollonius .

Geometrie

După teorema lui Steinitz, graful Goldner-Harari este un graf poliedric - este plan și 3-conectat, deci există un poliedru convex care are ca schelet  graful Goldner-Harari .

Din punct de vedere geometric, reprezentarea poliedrică a grafului Goldner-Harari poate fi formată prin lipirea unui tetraedru de fiecare față a unei bipiramide triunghiulare , în același mod în care se formează un triakistetraedru prin lipirea unui tetraedru de fiecare față a unui octaedru . Adică este un poliedru Klee al unei dipiramide triunghiulare [4] [7] . Graficul dual al contelui Goldner-Harari este reprezentat geometric prin trunchierea unei prisme triunghiulare .

Proprietăți algebrice

Grupul de automorfism al graficului Goldner-Harari are ordinul 12 și este izomorf cu grupul diedric D 6 , grupul de simetrie al unui hexagon regulat care include atât rotații, cât și reflexii.

Polinomul caracteristic al graficului Goldner-Harari este .

Note

1. ↑ A. Goldner, F. Harary. {{{titlu}}} // Bull. Matematică malaeziană. Soc.. - 1975. - V. 6 , nr. 1 . — S. 41–42 . . Vezi, de asemenea, numerele 6 (2):33 (1975) şi 8 :104-106 (1977). Link-uri din lista de site-uri a publicațiilor lui Harari Arhivate 2 ianuarie 2013 la Wayback Machine .
2. ↑ M. B. Dillencourt. Poliedre de ordine mici și proprietățile hamiltoniene ale acestora // Journal of Combinatorial Theory, Seria B. - 1996. - V. 66 . — S. 87–122 . - doi : 10.1006/jctb.1996.0008 . .
3. ↑ RC Read, RJ Wilson. Un atlas de grafice. - Oxford, Anglia: Oxford University Press, 1998. - S. 285. .
4. ↑ 1 2 Branko Grünbaum. Politopi convexe. - Wiley Interscience, 1967. - S. 357. .
5. ↑ Frank R. Bernhart, Paul C. Kainen. Grosimea cărții a unui grafic. - Journal of Combinatorial Theory, Seria B. - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
6. ↑ Mihalis Yannakakis. Proc. Al 18-lea ACM Symp. Teoria calculului (STOC). - 1986. - S. 104-108. - doi : 10.1145/12130.12141 . .
7. ↑ Gunter Ewald. Circuite hamiltoniene în complexe simple // Geometriae Dedicata. - 1973. - Vol. 2 , numărul. 1 . — S. 115–125 . - doi : 10.1007/BF00149287 . .

Link -uri

• Weisstein, Eric W. Goldner-Harary grafic  (engleză) pe site-ul web Wolfram MathWorld .