12článková Tatta

Tuttův 12-buněčný ( Bensonův graf [1] ) je 3- pravidelný graf se 126 vrcholy a 189 hranami, pojmenovaný po Williamu Tuttovi [2] .

Je jediná (3-12)- buňka [3] ; má chromatické číslo 2 ( bipartitní ), chromatický index 3, obvod 12 (jako 12článkový) a průměr 6; počet křižovatek je 170 a je předpoklad, že tento graf je při daném počtu křižovatek minimální [4] [5] .

Objevil jej Clark Benson v roce 1966 [6] .

Budova

Tuttova 12-buňka je kubický hamiltonovský graf a lze jej definovat pomocí LCF kódu [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57 , 11, −21, −57, 59, −17] 7 [7] .

Jak dokázali Cohen a Tits, až do izomorfismu existují přesně dva zobecněné šestiúhelníky řádu (2,2) . Jedná se o zlomený Cayleyův šestiúhelník H(2) a jeho duál (po bodech/čarách). Je jasné, že oba mají stejný graf incidence, který je ve skutečnosti izomorfní k Tuttově 12-buňce [1] .

Balaban 11-buňka může být zkonstruována odříznutím malého podstromu z Tutt 12-buňky a vymazáním výsledných vrcholů druhého stupně [8] .

Algebraické vlastnosti

Skupinový automorfismus Tutt 12-buňky má řád 12096 a je polopřímým součinem projektivní speciální unitární grupy PSU(3,3) s cyklickou grupou Z /2 Z [1] . Skupina působí tranzitivně na hranách, ale ne na vrcholech, což z ní činí semisymetrický graf , pravidelný graf, který je přechodově přechodný , ale ne vertexově tranzitivní . Ve skutečnosti automorfismus Tutt 12-buněčných skupin zachovává části grafu a působí jednoduše na každou z nich. Takové grafy se nazývají biprimitivní a existuje pouze pět kubických biprimitivních grafů. Říká se jim Ivanov-Iofinovy ​​grafy a mají řády 110, 126, 182, 506 a 990 [9] .

Jsou známy všechny kubické semisymetrické grafy obsahující až 768 vrcholů. Podle Kondera, Malnic, Marusice a Potočnika je 12článkový Tutta jediným semisymetrickým grafem se 126 vrcholy a pátým nejmenším možným kubickým semisymetrickým grafem po Grayově grafu , grafu Ivanov-Iofinova se 110 vrcholy , lublaňském grafu, a 120-vertexový graf s obvodem 8 [10] .

Charakteristický polynom 12-buněčného Tatta je roven

Graf je jediný s tímto charakteristickým polynomem, takže 12-článkový je definován svým spektrem .

Galerie

• Chromatické číslo 12článkového Tatta je 2.

• Chromatický index 12-článkového Tatta je 3.

Poznámky

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

Literatura

• Benson CT Minimální pravidelné grafy obvodu 8 a 12 // Can. J. Math .. - 1966. - Vydání. 18 .
• Exoo G. Přímočaré kresby slavných grafů . — 2006.
• Pegg ET, Exoo G. Crossing Number Graphs // Mathematica J.. - 2009. - Vol. 11 .
• Polster BA geometrická obrázková kniha. - New York: Springer Science + Business Media, LLC, 1998. - (Universitex). — ISBN 978-1-4612-6426-2 . - ISBN 978-1-4619-8526-2 .
• Balaban AT Trivalentní grafy obvodu devět a jedenáct a vztahy mezi klecemi // Rev. Roumainská matematika. - 1973. - Vydání. 18 .
• Geoffrey Exoo, Robert Jajcay. Dynamický průzkum klecí // Elektr. J. Combin. - 2008. - Vydání. 15 .
• Ivanov A. A., Iofinova M. E. Biprimitivní kubické grafy // Studie algebraické teorie kombinatorických objektů. - M. , 1985. - S. 137-152. - (Série: Všeruský výzkumný ústav pro systémový výzkum. Sborník příspěvků ze semináře).
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Sčítání semisymetrických kubických grafů až na 768 vrcholech // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .