Greve av Herschel

Greve av Herschel
Döpt efter A. S. Herschel
Toppar elva
revben arton
Radie 3
Diameter fyra
Omkrets fyra
Automorfismer 12 ( D6 )
Kromatiskt nummer 2
Kromatiskt index fyra
Egenskaper

polyedrisk
plan
dikot


perfekt
 Mediafiler på Wikimedia Commons

I grafteorin är Herschel-grafen  en tvådelad oriktad graf med 11 hörn och 18 kanter, den minsta icke-Hamiltonska polyedriska grafen. Grafen är uppkallad efter den brittiske astronomen A. S. Herschel , som skrev ett tidigt arbete om Ikosian-spelet av William Rowan Hamilton  - Herschel-grafen ger den minsta konvexa polyedern som spelet inte har någon lösning på. Men Herschels artikel beskriver lösningar för spelet "Ikosian" endast för tetraedern och icosahedronen , och beskriver inte Herschels graf [1] .

Egenskaper

Herschel- grafen är plan  - den kan ritas på ett plan utan att korsa kanter. Den är också vertex-3-ansluten  — om du tar bort två valfria hörn lämnar subgrafen ansluten. Därför, enligt Steinitz-satsen , Goldner-grafen - Harari är en polyedrisk graf  - det finns en konvex polyeder ( enneahedron ) som har Herschel-grafen som sitt skelett [2] . Herschel-grafen är också tvådelad  - dess hörn kan delas upp i två delmängder om fem och sex hörn så att varje kant har ändpunkter i båda uppsättningarna (röda och blå delmängder i figuren).

Liksom alla andra tvådelade grafer är Herschel-grafen perfekt  - det kromatiska numret för alla genererade subgrafer är lika med storleken på den största klicken i denna subgraf. Grafen har kromatiskt index 4, omkrets 4, radie 3 och diameter 4.

Hamiltonian

Eftersom grafen är tvådelad och har ett udda antal hörn, innehåller den inte en Hamiltonsk cykel (en cykel av kanter som passerar genom varje vertex exakt en gång). I alla tvådelade grafer måste varje cykel växelvis passera genom båda uppsättningarna av hörn, och måste därför innehålla lika många hörn av båda typerna och ha en jämn längd. Således kan en cykel som går genom var och en av de elva hörnen inte existera. En graf är en minimal icke-Hamiltonsk polyedrisk graf, oavsett hur storleken på grafen mäts - med antalet hörn, kanter eller ytor [3] . Det finns en annan polyedrisk graf med 11 hörn som inte har Hamiltonska cykler (nämligen Goldner-Harari-grafen [4] ), men det finns ingen graf med mindre (eller lika många) kanter [2] .

Alla hörn av Herschel-grafen, med undantag för tre, har grad tre. Tates gissning [5] säger att en polyedrisk graf där vilken vertex som helst har grad tre måste vara Hamiltonian, men den motbevisas av Tutts motexempel, Tutts mycket större graf [6] . En uppdatering av Tutts gissning, Barnetts gissning att alla tvådelade 3-regelbundna polyedriska grafer är Hamiltonska, förblir öppen [7] .

Herschel-grafen ger också ett exempel på en polyedrisk graf där den mittersta grafen inte kan delas upp i två icke-korsande Hamilton-cykler. Den mellersta grafen i Herschel-grafen är en 4- regelbunden graf med 18 hörn, en för varje kant av Herschel-grafen. Två hörn är intill varandra i en mediangraf om de motsvarande kanterna på Herschel-grafen går sekventiellt på en av dess ytor [8] .

Algebraiska egenskaper

Herschel-grafen är inte vertextransitiv och dess fullständiga automorfismgrupp är isomorf till ordningen 12 dihedrisk grupp , symmetrigruppen för en regelbunden hexagon , inklusive både rotationer och reflektioner. Varje permutation av dess hörn av fjärde graden kan representeras av en grafautomorfism, och det finns också en icke-trivial automorfism som permuterar de återstående hörnen utan att påverka hörnen i den fjärde graden.

Det karakteristiska polynomet i Herschel-grafen är .

Anteckningar

  1. ↑ AS Herschel. Sir Wm. Hamilton's Icosian Game  // The Quarterly Journal of Pure and Applied Mathematics . - 1862. - T. 5 . - S. 305 .
  2. ↑ 1 2 H. S. M. Coxeter. Vanliga polytoper . - Dover, 1973. - S.  8 .
  3. ↑ David Barnette, Ernest Jucovic. Hamiltonska kretsar på 3-polytoper // 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  på Wolfram MathWorld -webbplatsen .
  5. ↑ P.G. Tait. Listans topologi  // Filosofisk tidskrift (5:e ser.). - 1884. - T. 17 . - S. 30-46 . . Omtryckt i Scientific Papers , Vol. II, sid. 85-98.
  6. ↑ WT Tutte. På Hamiltonska kretsar  // 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. Barnettes gissning . — den öppna problemträdgården, 11 juni 2007.
  8. ↑ JA Bondy, R. Häggkvist. Kant-disjunkt Hamilton cykler i 4-regelbundna plana grafer // Aequationes Mathematicae. - 1981. - T. 22 , nr. 1 . - S. 42-45 . - doi : 10.1007/BF02190157 .

Länkar