Greve af Herschel

Greve af Herschel
Opkaldt efter A. S. Herschel
Toppe elleve
ribben atten
Radius 3
Diameter fire
Omkreds fire
Automorfismer 12 ( D6 )
Kromatisk tal 2
Kromatisk indeks fire
Ejendomme

polyedrisk
plan
dikot


Perfekt
 Mediefiler på Wikimedia Commons

I grafteorien er Herschel-grafen  en todelt urettet graf med 11 hjørner og 18 kanter, den mindste ikke-Hamiltonske polyedriske graf. Grafen er opkaldt efter den britiske astronom A. S. Herschel , som skrev et tidligt værk om det Ikosiske spil af William Rowan Hamilton  - Herschel-grafen giver det mindste konvekse polyeder , som spillet ikke har nogen løsning på. Herschels artikel beskriver dog kun løsninger til spillet "Ikosian" for tetraeder og icosahedron , og beskriver ikke Herschels graf [1] .

Egenskaber

Herschel -grafen er plan  - den kan tegnes på et plan uden at krydse kanter. Den er også vertex-3-forbundet -  fjernelse af to vilkårlige spidser efterlader undergrafen forbundet. Derfor, ifølge Steinitz-sætningen , er Goldner-grafen - Harari er en polyhedral graf  - der er et konveks polyeder ( enneahedron ) med Herschel-grafen som skelet [2] . Herschel-grafen er også todelt  - dens toppunkter kan opdeles i to delmængder af fem og seks hjørner, således at hver kant har endepunkter i begge sæt (røde og blå delmængder i figuren).

Som enhver anden todelt graf er Herschel-grafen perfekt  - det kromatiske tal for enhver genereret undergraf er lig med størrelsen af ​​den største klike i denne undergraf. Grafen har kromatisk indeks 4, omkreds 4, radius 3 og diameter 4.

Hamiltonian

Da grafen er todelt og har et ulige antal hjørner, indeholder den ikke en Hamiltonsk cyklus (en cyklus af kanter, der passerer gennem hvert hjørne nøjagtigt én gang). I enhver todelt graf skal en hvilken som helst cyklus skiftevis passere gennem begge sæt af hjørner og skal derfor indeholde lige mange hjørner af begge typer og have en lige længde. En cyklus, der går gennem hvert af de elleve hjørner, kan således ikke eksistere. En graf er en minimal ikke-hamiltonsk polyhedral graf, uanset hvordan størrelsen af ​​grafen måles - ved antallet af hjørner, kanter eller flader [3] . Der er en anden polyedrisk graf med 11 hjørner, der ikke har Hamiltonske cyklusser (nemlig Goldner-Harari grafen [4] ), men der er ingen graf med mindre (eller lige meget) antal kanter [2] .

Alle hjørner af Herschel-grafen, med undtagelse af tre, har grad tre. Tates formodning [5] siger, at en polyedrisk graf, hvor ethvert toppunkt har grad tre , skal være Hamiltonsk, men det afvises af Tutts modeksempel, Tutts meget større graf [6] . En opdatering af Tutts formodning, Barnetts om at enhver todelt 3-regulær polyhedral graf er Hamiltonsk, forbliver åben [7] .

Herschel-grafen giver også et eksempel på en polyedrisk graf, for hvilken den midterste graf ikke kan opdeles i to ikke-krydsende Hamilton-cyklusser. Den midterste graf på Herschel-grafen er en 4 -regulær graf med 18 hjørner, en for hver kant af Herschel-grafen. To hjørner støder op til hinanden i en mediangraf, hvis de tilsvarende kanter på Herschel-grafen går sekventielt på en af ​​dens flader [8] .

Algebraiske egenskaber

Herschel-grafen er ikke vertex-transitiv , og dens fulde automorfi-gruppe er isomorf til rækkefølgen 12 dihedral gruppe , symmetrigruppen af ​​en regulær sekskant , inklusive både rotationer og refleksioner. Enhver permutation af dens hjørner af fjerde grad kan repræsenteres af en grafautomorfi, og der er også en ikke-triviel automorfi, der permuterer de resterende hjørner uden at påvirke hjørnerne i fjerde grad.

Det karakteristiske polynomium af Herschel-grafen er .

Noter

  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. Almindelige polytoper . - Dover, 1973. - S.  8 .
  3. ↑ David Barnette, Ernest Jucovic. Hamiltonske kredsløb på 3-polytoper // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 1 . - S. 54-59 . - doi : 10.1016/S0021-9800(70)80054-0 .
  4. ↑ Weisstein, Eric W. Goldner-Harary Graph  på Wolfram MathWorld -webstedet .
  5. ↑ P.G. Tait. Fortegnelsens Topologi  // Filosofisk Tidsskrift (5. ser.). - 1884. - T. 17 . - S. 30-46 . . Genoptrykt i Scientific Papers , Vol. II, s. 85-98.
  6. ↑ WT Tutte. Om Hamiltonske kredsløb  // 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 formodning . — den åbne problemhave, 11. juni 2007.
  8. ↑ JA Bondy, R. Häggkvist. Kant-disjunkte Hamilton cykler i 4-regulære plane grafer // Aequationes Mathematicae. - 1981. - T. 22 , no. 1 . - S. 42-45 . - doi : 10.1007/BF02190157 .

Links