12 cellás Tatta

A Tutt-féle 12 cellás ( Benson-gráf [1] ) egy 126 csúcsból és 189 élből álló 3 szabályos gráf , amelyet William Tuttról neveztek el [2] .

Az egyetlen (3-12)- cella [3] ; kromatikus száma 2 ( kétrészes ), kromatikus indexe 3, kerülete 12 (12 cellaként), átmérője 6; a metszéspontok száma 170, és feltételezzük, hogy ez a grafikon adott számú metszéspont mellett minimális [4] [5] .

Clark Benson fedezte fel 1966-ban [6] .

Épület

A Tutt 12-cella egy köbös Hamilton -gráf, és az LCF kóddal definiálható [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57 , 11, −21, −57, 59, −17] 7 [7] .

Ahogy Cohen és Tits bebizonyította, az izomorfizmusig pontosan két általánosított hatszög van a (2,2) sorrendben . Ezek a törött Cayley hatszög H(2) és a kettős (pontok/vonalak). Nyilvánvaló, hogy mindkettőnek ugyanaz az előfordulási gráfja, ami valójában izomorf Tutt 12 cellájával [1] .

A Balaban 11-cellát úgy lehet megszerkeszteni, hogy a Tutt 12-es cellából levágunk egy kis részfát, és töröljük a kapott második fokú csúcsokat [8] .

Algebrai tulajdonságok

A Tutt 12-cella csoportautomorfizmusának rendje 12096, és a projektív speciális unitárius csoport PSU(3,3) félig közvetlen szorzata a Z /2 Z ciklikus csoporttal [1] . A csoport tranzitív módon hat az élekre, de nem a csúcsokra, így félszimmetrikus gráf lesz , egy reguláris gráf, amely éltranzitív , de nem csúcstranzitív . Valójában a Tutt 12 sejtes csoport automorfizmusa megőrzi a gráf részeit, és egyszerűen mindegyikre hat. Az ilyen gráfokat biprimitívnek nevezzük, és csak öt köbös biprimitív gráf létezik. Ezeket Ivanov-Iofinova gráfoknak nevezik, és sorrendjük 110, 126, 182, 506 és 990 [9] .

Minden legfeljebb 768 csúcsot tartalmazó köbös félszimmetrikus gráf ismert. Konder, Malnic, Marusic és Potočnik szerint a 12 cellás Tutta az egyetlen 126 csúcsú félszimmetrikus gráf, és az ötödik legkisebb köbös félszimmetrikus gráf a Gray gráf , a 110 csúcsos Ivanov-Iofinova gráf , a Ljubljana gráf után. és a 120 csúcsú gráf 8-as kerülettel [10] .

A 12 cellás Tatta karakterisztikus polinomja egyenlő

A gráf az egyetlen ilyen karakterisztikus polinommal, így a 12 cellát a spektruma határozza meg .

Galéria

• A 12 cellás Tatta kromatikus száma 2.

• A 12 sejtes Tatta kromatikus indexe 3.

Jegyzetek

1. ↑ 1 2 3 Exoo, Jajcay, 2008 .
2. ↑ Weisstein, Eric W. Tutte 12 ketrec  a Wolfram MathWorld weboldalán .
3. ↑ OEIS szekvencia A052453 _
4. ↑ Exoo, 2006 .
5. ↑ Pegg, Exoo, 2009 .
6. ↑ Benson, 1966 , p. 1091-1094.
7. ↑ Polster, 1998 , p. 179.
8. ↑ Balaban, 1973 , p. 1033-1043.
9. ↑ Ivanov, Iofinova, 1985 , p. 123-134.
10. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255–294.

Irodalom

• Benson CT Minimális reguláris grafikonok a 8. és 12. kerületről // Can. J. Math .. - 1966. - Kiadás. 18 .
• Exoo G. Híres grafikonok egyenes vonalú rajzai . – 2006.
• Pegg ET, Exoo G. Crossing Number Graphs // Mathematica J.. - 2009. - Vol. 11 .
• Polster BA geometriai képeskönyv. - New York: Springer Science + Business Media, LLC, 1998. - (Universitex). — ISBN 978-1-4612-6426-2 . - ISBN 978-1-4619-8526-2 .
• Balaban AT Trivalens Graphs of Girth Nine és Ele1 és Relationships among the Cages // Rev. Roumaine Math. - 1973. - Kiadás. 18 .
• Geoffrey Exoo, Robert Jajcay. Dinamikus ketrec felmérés // Electr. J. Combin. - 2008. - Kiadás. 15 .
• Ivanov A. A., Iofinova M. E. Biprimitív köbös gráfok // Tanulmányok a kombinatorikus objektumok algebrai elméletében. - M. , 1985. - S. 137-152. - (Sorozat: Összoroszországi Rendszerkutatási Kutatóintézet. A szeminárium anyaga).
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Félszimmetrikus köbös gráfok összeírása akár 768 csúcson // Journal of Algebraic Combinatorics. - 2006. - T. 23 . – S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .