Graficul Goldner-Harary

Graficul Goldner-Harary este un grafic nedirecționat cu 11 vârfuri și 27 de muchii . Acesta poartă numele matematicienilor A. Goldner și Frank Harary, care au demonstrat în 1975 că este cel mai mic grafic planar maxim de tip non-hamiltonian . ^[1] ^[2] ^[3] Același grafic fusese deja indicat ca exemplu de poliedru simplicial non-hamiltonian de către Branko Grünbaum în 1967. ^[4]

Are un număr cromatic de 4, un indice cromatic de 8, o circumferință de 3, o rază de 2, un diametru egal cu 2 și este un grafic cu 3 margini. Mai mult, este un arbore cu lungimea egală cu 3: ca orice arborele k , este, de asemenea, un grafic chordal și, ca grafic plan de tip "3-copac" (arborele ternar), este un exemplu de rețea apoloniană.

Proprietate

Graficul Goldner-Harary este plan, deoarece poate fi trasat pe plan fără a-i traversa marginile. În plus, este de tip plan maxim, deoarece toate fețele sale sunt triunghiulare , atunci când sunt trasate într-un plan. La fel ca orice grafic plan maxim, este, de asemenea, k-conectat la 3 vârfuri ( $k=3$ ${\ displaystyle k = 3}$ ${\ displaystyle k = 3}$ ), adică un subgraf conectat rămâne chiar dacă unul sau două dintre vârfurile sale sunt îndepărtate: pentru a deveni deconectate trebuie să fie eliminate 3 vârfuri sau 3 muchii.

Deoarece cel mai mic număr posibil de vârfuri pentru un grafic poliedric non-hamiltonian este 11, graficul Goldner-Harary este un grafic plan maxim cu numărul minim de vârfuri, dar fără margini: de fapt, graficul Herschel este un non-poliedru. Hamiltonian având 11 vârfuri și 18 muchii, în loc de 27.

Ca un complot plan non-hamiltonian maxim, graficul Goldner - Harary oferă un exemplu de grafic plan cu o grosime de carte mai mare de două. ^[5] Pe baza existenței unor astfel de exemple, Bernhart și Kainen au emis ipoteza că grosimea cărții a diagramelor plane ar putea fi făcută în mod arbitrar mare, dar au fost ulterior respinse de demonstrația că toate diagramele plane au grosimea cărții mai mică sau mai mică. Egală cu 4 . ^[6]
În special, graficul Goldner - Harary are o grosime de carte de 3.

Geometrie

Conform teoremei lui Steinitz, graficul Goldner-Haray este un grafic poliedric: deoarece este plan și este un arbore ternar, există un poliedru convex care poate avea graficul Goldner-Harary ca propriul său n-schelet, având n topologic subspatii obtinute in cat mai multi pasi discreti.

Un poliedru reprezentând graficul Goldner-Harary poate fi construit prin lipirea unui tetraedru pe fiecare dintre cele trei fețe ale unei piramide triunghiulare, similar modului în care se obține un triacizoctaedru prin lipirea unui tetraedru pe fiecare față a unui octaedru : este „Kleetopo „ a unei piramide triunghiulare. ^[4] ^[7] dualul graficului Goldner-Harary este reprezentat printr - un punct de vedere geometric trunchiată triunghiular prisme .

Culoare

Numărul cromatic este 4, care este cea mai mică valoare posibilă pentru care graficul poate fi colorat în așa fel încât orice pereche de vârfuri conectate printr-o margine să aibă întotdeauna culori diferite.

Indicele cromatic al graficului Goldner-Harary este 8, care este numărul minim de culori aplicabil marginilor în așa fel încât orice pereche de margini incidente (care insistă) pe același vârf să nu aibă niciodată aceeași culoare.

Este posibil să se numere diferitele culori ale graficului Goldner-Harary. Este descris în raport cu numărul de culori permis de o funcție polinomială asociată cu polinomul cromatic , care este un polinom de grad 11, care acceptă ca posibile rădăcini toate numerele întregi pozitive sau nule strict mai mici de 4. Este egal cu: $(x-3)^{8}(x-2)(x-1)x$ ${\ displaystyle (x-3) ^ {8} (x-2) (x-1) x}$ ${\ displaystyle (x-3) ^ {8} (x-2) (x-1) x}$ .

Proprietăți algebrice

Grupul de automorfism al graficului Goldner-Harary este un grup de ordin 12 izomorf în raport cu grupa diedrică D6, grupul de izometrii din plan care formează un hexagon regulat. Acest grup este compus din 6 elemente corespunzătoare rotațiilor și alte 6 corespunzătoare reflexiilor plane.

Polinomul caracteristic al matricei de adiacență a unui grafic Goldner-Harary este următorul: $-(x-1)^{2}x^{2}(x+2)^{3}(x^{2}-3)(x^{2}-4x-9)$ ${\ displaystyle - (x-1) ^ {2} x ^ {2} (x + 2) ^ {3} (x ^ {2} -3) (x ^ {2} -4x-9)}$ ${\ displaystyle - (x-1) ^ {2} x ^ {2} (x + 2) ^ {3} (x ^ {2} -3) (x ^ {2} -4x-9)}$ .

Notă

^ A. Goldner și F. Harary , Notă asupra unui cel mai mic grafic plan nonhamiltonian maxim , în Bull. Matematica Malaeziană. Soc. , Vol. 6, nr. 1, 1975, pp. 41–42. . A se vedea, de asemenea, același jurnal 6 (2): 33 (1975) și 8 : 104-106 (1977). Referință din lista de publicații a lui Harary .
^ Dillencourt, MB, Poliedre de ordine mici și proprietățile lor hamiltoniene , în Journal of Combinatorial Theory, Seria B , vol. 66, 1996, pp. 87–122, DOI : 10.1006 / jctb.1996.0008 . .
^ RC Read și RJ Wilson, An Atlas of Graphs , Oxford, Anglia, Oxford University Press, 1998, p. 285 ..
^ ^a ^b Branko Grünbaum, Convex Polytopes , Wiley Interscience, 1967, p. 357 .. Texte postuniversitare în matematică 221, Springer-Verlag, 2003, ISBN 978-0-387-40409-7 , p. 357, ediția a II-a.
^ Frank R. Bernhart și Paul C. Kainen, Grosimea cărții unui grafic , în Journal of Combinatorial Theory , Seria B, vol. 27, n. 3, 1979, pp. 320–331, DOI : 10.1016 / 0095-8956 (79) 90021-2 . . A se vedea în special Figura 9.
^ Mihalis Yannakakis, Patru pagini sunt necesare și suficiente pentru graficele plane , în Proc. 18 ACM Symp. Teoria calculelor (STOC) , 1986, pp. 104-108, DOI : 10.1145 / 12130.12141 . .
^ Günter Ewald, Circuite hamiltoniene în complexe simpliciale , în Geometriae Dedicata , vol. 2, nr. 1, 1973, pp. 115–125, DOI : 10.1007 / BF00149287 . .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe Goldner-Harary Graph

linkuri externe

(RO) Eric W. Weisstein , Goldner-Harary Graph pe MathWorld .

Portal IT

Portalul de matematică

[1] A. Goldner și F. Harary , Notă asupra unui cel mai mic grafic plan nonhamiltonian maxim , în Bull. Matematica Malaeziană. Soc. , Vol. 6, nr. 1, 1975, pp. 41–42. . A se vedea, de asemenea, același jurnal 6 (2): 33 (1975) și 8 : 104-106 (1977). Referință din lista de publicații a lui Harary .

[2] Dillencourt, MB, Poliedre de ordine mici și proprietățile lor hamiltoniene , în Journal of Combinatorial Theory, Seria B , vol. 66, 1996, pp. 87–122, DOI : 10.1006 / jctb.1996.0008 . .

[3] RC Read și RJ Wilson, An Atlas of Graphs , Oxford, Anglia, Oxford University Press, 1998, p. 285 ..

[grun-4] Branko Grünbaum, Convex Polytopes , Wiley Interscience, 1967, p. 357 .. Texte postuniversitare în matematică 221, Springer-Verlag, 2003, ISBN 978-0-387-40409-7 , p. 357, ediția a II-a.

[5] Frank R. Bernhart și Paul C. Kainen, Grosimea cărții unui grafic , în Journal of Combinatorial Theory , Seria B, vol. 27, n. 3, 1979, pp. 320–331, DOI : 10.1016 / 0095-8956 (79) 90021-2 . . A se vedea în special Figura 9.

[6] Mihalis Yannakakis, Patru pagini sunt necesare și suficiente pentru graficele plane , în Proc. 18 ACM Symp. Teoria calculelor (STOC) , 1986, pp. 104-108, DOI : 10.1145 / 12130.12141 . .

[ewald-7] Günter Ewald, Circuite hamiltoniene în complexe simpliciale , în Geometriae Dedicata , vol. 2, nr. 1, 1973, pp. 115–125, DOI : 10.1007 / BF00149287 . .

[1]

[2]

[3]

[4]

[5]

[6]

[7]