Greve Goldner - Harari

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 mars 2022; verifiering kräver 1 redigering .
Greve Goldner - Harari
Döpt efter A. Goldner, F. Harari
Toppar elva
revben 27
Radie 2
Diameter 2
Omkrets 3
Automorfismer 12 ( D6 )
Kromatiskt nummer fyra
Kromatiskt index åtta
Egenskaper

polyedrisk
plan
ackord
perfekt


träbredd = 3
 Mediafiler på Wikimedia Commons

I grafteorin är Goldner-Harari-grafen  en enkel oriktad graf med 11 hörn och 27 kanter. Filen är uppkallad efter A. Goldner och F. Harari , som bevisade 1975 att det är den minsta icke-Hamiltonska maximala plana grafen [1] [2] [3] . Samma graf gavs redan som ett exempel på en icke-hamiltonsk enkel polytop av Grünbaum 1967. [4]

Egenskaper

Goldner-grafen är Harari- plan  - den kan ritas på ett plan utan att korsa kanter. När den ritas på planet är alla grafens ytor triangulära, vilket gör den till en maximal plan graf . Liksom vilken maximal plan graf som helst, är den också 3-vertex-ansluten  - om du tar bort två hörn lämnar subgrafen ansluten.

Earlen av Goldner är Harari för icke-Hamiltonianerna . Minsta möjliga antal hörn för icke-Hamiltonska polyedriska grafer är 11. Goldner-Harari-grafen är alltså ett exempel på en minimal graf av denna typ. Men Herschel-grafen , en annan icke-Hamiltonisk polyeder med 11 hörn, har färre kanter.

Som en maximal plan icke-Hamilton-graf ger Goldner-Harari-grafen ett exempel på en plan graf med en boktjocklek som är större än två [5] . Baserat på förekomsten av sådana exempel, antog Bernhart och Kainen (Bernhart, Kainen) att boktjockleken för plana grafer kan vara godtyckligt stor, men då visades det att alla plana grafer har en boktjocklek som inte överstiger fyra [6] .

Grafens boktjocklek är 3, det kromatiska talet är 4, det kromatiska indexet är 8, omkretsen är 3, radien är 2, diametern är 2 och grafen är 3-kantsansluten .

Grafen är också ett 3-träd , så dess trädbredd är 3. Som alla k - träd är grafen ackordal . Som ett plant 3-träd ger grafen ett exempel på ett Apollonius-nätverk .

Geometri

Enligt Steinitzs teorem är Goldner-Harari-grafen en polyedrisk graf  - den är plan och 3-kopplad, så det finns en konvex polyeder som har Goldner-Harari-grafen som sitt skelett .

Geometriskt kan den polyedriska representationen av Goldner-Harari-grafen bildas genom att limma en tetraeder på varje sida av en triangulär bipyramid , på samma sätt som en triakistetraeder bildas genom att limma en tetraeder på varje sida av en oktaeder . Det vill säga, det är en Klee-polyeder av en triangulär dipyramid [4] [7] . Den dubbla grafen för greve Goldner-Harari representeras geometriskt av trunkeringen av ett triangulärt prisma .

Algebraiska egenskaper

Automorfismgruppen i Goldner-Harari-grafen har ordning 12 och är isomorf till den dihedriska gruppen D 6 , symmetrigruppen för en regelbunden hexagon som inkluderar både rotationer och reflektioner.

Det karakteristiska polynomet i Goldner-Harari-grafen är .

Anteckningar

  1. ↑ A. Goldner, F. Harary. {{{title}}} // Bull. Malaysisk matematik. Soc.. - 1975. - V. 6 , nr. 1 . — S. 41–42 . . Se även nummer 6 (2):33 (1975) och 8 :104-106 (1977). Länkar från webbplatslistan över Hararis publikationer Arkiverad 2 januari 2013 på Wayback Machine .
  2. ↑ M. B. Dillencourt. Polyedra av små beställningar och deras Hamiltonska egenskaper // Journal of Combinatorial Theory, Series B. - 1996. - V. 66 . — S. 87–122 . - doi : 10.1006/jctb.1996.0008 . .
  3. ↑ RC Read, RJ Wilson. En atlas av grafer. - Oxford, England: Oxford University Press, 1998. - S. 285. .
  4. ↑ 1 2 Branko Grünbaum. Konvexa polytoper. - Wiley Interscience, 1967. - S. 357. .
  5. ↑ Frank R. Bernhart, Paul C. Kainen. Bokens tjocklek på en graf. - Journal of Combinatorial Theory, Series B. - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
  6. ↑ Mihalis Yannakakis. Proc. 18:e ACM Symp. Theory of Computing (STOC). - 1986. - S. 104-108. - doi : 10.1145/12130.12141 . .
  7. ↑ Gunter Ewald. Hamiltonska kretsar i enkla komplex // Geometriae Dedicata. - 1973. - Vol. 2 , nummer. 1 . — S. 115–125 . - doi : 10.1007/BF00149287 . .

Länkar