Contele de Herschel

În teoria grafurilor, graful Herschel  este un graf bipartit nedirecționat cu 11 vârfuri și 18 muchii, cel mai mic graf poliedric non-Hamiltonian . Graficul este numit după astronomul britanic A. S. Herschel , care a scris o lucrare timpurie despre jocul Ikosian de William Rowan Hamilton  - graficul Herschel oferă cel mai mic poliedru convex pentru care jocul nu are nicio soluție. Totuși, articolul lui Herschel descrie soluții pentru jocul „Ikosian” doar pentru tetraedru și icosaedru și nu descrie graficul lui Herschel [1] .

Proprietăți

Graficul Herschel este plan  - poate fi desenat pe un plan fără margini încrucișate. Este, de asemenea , conectat la vârf 3 -  eliminarea oricăror două vârfuri lasă subgraful conectat. Prin urmare, conform teoremei Steinitz , graful Goldner - Harari este un graf poliedric  - există un poliedru convex ( enneaedru ) având ca schelet graficul Herschel [2] . Graficul Herschel este, de asemenea, bipartit  - vârfurile sale pot fi împărțite în două subseturi de cinci și șase vârfuri, astfel încât fiecare muchie să aibă puncte finale în ambele seturi (subseturi roșii și albastre din figură).

Ca orice alt graf bipartit, graficul Herschel este perfect  - numărul cromatic al oricărui subgraf generat este egal cu dimensiunea celei mai mari clicuri a acestui subgraf. Graficul are indicele cromatic 4, circumferința 4, raza 3 și diametrul 4.

Hamiltonian

Deoarece graficul este bipartit și are un număr impar de vârfuri, nu conține un ciclu hamiltonian (un ciclu de muchii care trece prin fiecare vârf exact o dată). În orice graf bipartit, orice ciclu trebuie să treacă alternativ prin ambele seturi de vârfuri și, prin urmare, trebuie să conțină un număr egal de vârfuri de ambele tipuri și să aibă o lungime pară. Astfel, un ciclu care trece prin fiecare dintre cele unsprezece vârfuri nu poate exista. Un graf este un graf poliedric minim non-Hamiltonian, indiferent de modul în care este măsurată dimensiunea graficului - prin numărul de vârfuri, muchii sau fețe [3] . Există un alt graf poliedric cu 11 vârfuri care nu are cicluri hamiltoniene (și anume, graful Goldner-Harari [4] ), dar nu există un graf cu un număr mai mic (sau egal) de muchii [2] .

Toate vârfurile grafului Herschel, cu excepția a trei, au gradul trei. Conjectura lui Tate [5] afirmă că un graf poliedric în care orice vârf are gradul trei trebuie să fie hamiltonian, dar este infirmat de contraexemplul lui Tutt , graficul mult mai mare al lui Tutt [6] . O actualizare a conjecturii lui Tutt, conjectura lui Barnett că orice graf poliedric bipartit 3-regular este hamiltonian, rămâne deschisă [7] .

Graficul Herschel oferă, de asemenea, un exemplu de grafic poliedric pentru care graficul din mijloc nu poate fi împărțit în două cicluri hamiltoniene neîncrucișate. Graficul din mijloc al graficului Herschel este un grafic regulat de 4 cu 18 vârfuri, câte unul pentru fiecare muchie a graficului Herschel. Două vârfuri sunt adiacente într-un graf median dacă muchiile corespunzătoare ale grafului Herschel merg secvenţial pe una dintre feţele sale [8] .

Proprietăți algebrice

Graficul Herschel nu este tranzitiv la vârf și grupul său de automorfism complet este izomorf la grupul diedric de ordinul 12 , grupul de simetrie al unui hexagon regulat , incluzând atât rotațiile, cât și reflexiile. Orice permutare a vârfurilor sale de gradul al patrulea poate fi reprezentată printr-un automorfism de graf și există, de asemenea, un automorfism non-trivial care permutează vârfurile rămase fără a afecta vârfurile gradului al patrulea.

Polinomul caracteristic al graficului Herschel este .

Note

1. ↑ AS Herschel. Domnul Wm. Jocul Icosian al lui Hamilton  // Jurnalul trimestrial de matematică pură și aplicată . - 1862. - T. 5 . - S. 305 .
2. ↑ 1 2 H. S. M. Coxeter. Politopuri obișnuite . - Dover, 1973. - P.  8 .
3. ↑ David Barnette, Ernest Jucovic. Circuite hamiltoniene pe 3-politopi // Journal of Combinatorial Theory. - 1970. - T. 9 , nr. 1 . - S. 54-59 . - doi : 10.1016/S0021-9800(70)80054-0 .
4. ^ Weisstein, Eric W. Goldner-Harary Graph pe site- ul Wolfram MathWorld .  
5. ↑ P.G. Tait. Topologia Listingului  // Revista Filosofică (ser. a 5-a). - 1884. - T. 17 . - S. 30-46 . . Reprinted in Scientific Papers , Vol. II, p. 85-98.
6. ↑ WT Tutte. Despre circuitele hamiltoniene  // Journal of the London Mathematical Society. - 1946. - T. 21 , nr. 2 . - S. 98-101 . - doi : 10.1112/jlms/s1-21.2.98 .
7. ↑ Robert Samal. Conjectura lui Barnette . — Grădina cu probleme deschise, 11 iunie 2007.
8. ↑ JA Bondy, R. Häggkvist. Cicluri Hamilton disjunse de muchii în grafice plane cu 4 regulate // Aequationes Mathematicae. - 1981. - T. 22 , nr. 1 . - S. 42-45 . - doi : 10.1007/BF02190157 .

Link -uri

• Weisstein, Eric W. Herschel Graph  (engleză) pe site-ul web Wolfram MathWorld .