Räkna Thatta

Räkna Thatta

Döpt efter	William Thomas Tutt
Toppar	46
revben	69
Radie	5
Diameter	åtta
Omkrets	fyra
Automorfismer	3 ( ) $\mathbb {Z} /3\mathbb {Z}$
Kromatiskt nummer	3
Kromatiskt index	3
Egenskaper	kubisk plan polyedrisk
Mediafiler på Wikimedia Commons

Tutta-grafen är ett exempel på en icke- hamiltonsk kubisk polyedrisk graf . Således tjänar den som ett motexempel till Tates gissning, som antog att vilken 3-regelbunden polytop som helst har en Hamiltonsk cykel [1] [2] .

Byggd av William Tutt 1946 [ 3] . Senare hittades andra motexempel, i de flesta fall baserade på Greenbergs sats .

Byggnad

Tatta-grafen består av tre identiska bitar, de så kallade Tatta-fragmenten. Ett fragment har egenskapen att av de tre kanterna som utgår från det, är en nödvändigtvis närvarande i Hamiltons cykel i vilken graf som helst med ett sådant fragment. "Obligatoriska" kanter av fragmentet närmar sig den centrala vertexen. Eftersom någon Hamilton-cykel bara kan använda två av dem, finns det ingen Hamilton-cykel.

Den resulterande grafen är 3-kopplad och plan , så enligt Steinitzs teorem är denna graf en polytopgraf. Grafen har 25 ansikten.

Geometriskt kan det erhållas från en tetraeder (varvid varje yta motsvarar fyra stora ytor med 9 kanter, varav tre är mellan par av fragment, och den fjärde bildar den yttre ytan) genom att upprepade gånger skära av tre av dess hörn.

Egenskaper

Den har 46 hörn och 69 kanter.
Det kromatiska numret på grafen är 3,
Kromatiskt index är 3,
omkretsen är 4
Diametern är 8.
Grafen är 3-kopplad och plan . Därför, enligt Steinitz-satsen , är denna graf en graf över en polyeder. (Antalet ansikten är 25.)
Gruppen av automorfismer i Tutt-grafen är , en cyklisk grupp av tredje ordningen. $\mathbb {Z} /3\mathbb {Z}$
Karakteristiskt polynom för grafen: $(x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^{9}+199x^{8} +1383x^{7}-576x^{6}-1061x^{5}+561x^{4}+233x^{3}-151x^{2}+4x+4)^{2}$ $(x^{15}+3x^{14}-16x^{13}-50x^{12}+94x^{11}+310x^{10}-257x^{9}-893x^{8 }+366x^{7}+1218x^{6}-347x^{5}-717x^{4}+236x^{3}+128x^{2}-56x+4)$ .

Variationer

Även om Tutta-grafen historiskt sett är den första 3-regelbundna icke-Hamiltonska polyedriska grafen, är den inte den minsta av dem.

1965 hittade Lederberg en graf med 38 hörn ( Barnett-Bosack-Lederberg-grafen ) [4] [5] ,
1968 byggde Greenberg flera motexempel till Tate-förmodan - Greenberg-grafer med 42, 44 och 46 hörn [6] , och 1974 hittades ytterligare två sådana grafer (Faulkner-Yanger-grafer) med 42 och 44 hörn [7] . 1988 fann man att det finns exakt sex icke-Hamiltonska polyedriska grafer med 38 hörn med icke-triviala sektioner av tre kanter, de bildas genom att ersätta två hörn av ett femkantigt prisma med samma fragment som användes i Tutts exempel [8 ] .

Anteckningar

↑ P.G. Tait. Listans topologi // Filosofisk tidskrift (5:e ser.). - 1884. - T. 17 . — S. 30–46 . . Artikel återgiven i Scientific Papers , Vol. II, sid. 85-98.
↑ 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 .
↑ Weisstein, Eric W. Tuttes graf på Wolfram MathWorld- webbplatsen .
↑ Lederberg, J. "DENDRAL-64: Ett system för datorkonstruktion, uppräkning och notering av organiska molekyler som trädstrukturer och cykliska grafer. Del II. Topologi av cykliska grafer. Delrapport till National Aeronautics and Space Administration. Bidrag NsG 81-60. 15 december 1965. [1] Arkiverad 20 maj 2014 på Wayback Machine
↑ Weisstein, Eric W. Barnette-Bosák-Lederberg Graf på Wolfram MathWorld -webbplatsen .
↑ E. Ya. Grinberg. Plana homogena grafer av grad tre utan Hamiltonska cykler. // lettv. matematik. årsbok. - T. 4 . — s. 51-58. .
↑ G. B. Faulkner, D. H. Yngre. Icke-Hamiltonska kubikplana kartor. // Diskret matematik . - 1974. - T. 7 . - S. 67-74 .
↑ D.A. Holton, B.D. McKay. De minsta icke-Hamiltonska 3-kopplade kubiska plana graferna har 38 hörn // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , nr. 3 . — S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .