12-клітка Татта

12-клітка Татта або граф Бенсона^[1], в теорії графів, є регулярним графом зі 126 вершинами і 189 ребрами, названий на честь Вільяма Татта.^[2]

12-Клітка Татта
The Tutte 12-cage
Названо на честь	Вільям Татт
Вершин	126
Ребер	189
Радіус	6
Діаметр	6
Обхват	12
Автоморфізм	12096
Хроматичне число	2
Хроматичний індекс	3
Властивості	Кубічний Теорія графів Гамільтонів граф Напівсиметричний Двочастковий

12-клітка Татта є унікальним клітинним графом (3-12) (послідовність A052453 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Він був відкритий Бенсоном у 1966 році^[3]. У цього графу хроматичне число дорівнює 2 (двочастковий), хроматичний індекс 3, обхват 12 (12-клітка) та його діаметр дорівнює 6. Цей граф має лише 170 схрещень, і Бенсон припустив, що це може бути найменший кубічний граф з таким числом схрещень.^[4][5]

Побудова

12-клітка Татта є кубічний Гамільтонів граф, тому його можна записати у LCF-нотації як [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17]^[6]

Як довели А. М. Коен і Жак Тітс^[en] з точністю до ізоморфізму існує рівно два узагальнених шестикутники порядку (2,2). Вони є розщепленням шестикутника Келі H(2) з дуальністю точка-відрізок. Очевидно, що обидва з них мають однакові графи інцидентності, який фактично ізоморфний 12-клітці Татта.^[1]

11-клітка Балабана може бути побудована шляхом усічення з 12-клітки Татта, видаляючи невелике дерево і пригнічуючи отримані вершини степеня два.^[7]

Алгебраїчні властивості

Група автоморфізмів 12-клітки Татта має порядок 12 096 і є напівпрямим добутком проективної спеціальної унітарної групи PSU(3,3) з циклічною групою Z/2Z.^[1] Вони діють транзитивно на його ребрах, але не на його вершинах, що робить його напівсиметричним графом, тобто регулярним графом, який є реберно-транзитивним, але не є вершинно-транзитивним. Фактично, група автоморфізмів Татта 12-клітки зберігає двоподільні частини і діє примітивно на кожній частині. Такі графи називаються бі-примітивними графами, і існує лише п'ять бі-примітивних кубічних графів; вони названі як графи Iofinova–Ivanov зі 110, 110, 126, 182, 506 і 990 вершинами.^[8]

Відомі всі кубічні напівсиметричні графи кількість вершин яких не перевищує 768. Згідно з Conder, Malnič, Marušič і Potočnik, 12-клітка Татта є єдиним кубічним напівсиметричним графом зі 126 вершинами і є п'ятим найменшим можливим кубічним напівсиметричним графом після графу Грея та графу Iofinova–Ivanov на 110 вершин, графу Любляни та графу на 120 вершин з обхватом 8.^[9]

Характеристичний поліном 12-клітки Татта:

${\displaystyle (x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}.}$

Це єдиний граф з таким характеристичним поліномом; тому, 12-клітка Татта визначається своїм спектром.

Галерея

• 
  Хроматичне число 12-клітки Татта дорівнює 2.
• 
  Хроматичний індекс 12-клітки Татта дорівнює 3.

Примітки

1. Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
2. Weisstein, Eric W. Tutte 12-cage(англ.) на сайті Wolfram MathWorld.
3. Benson, C. T. «Minimal Regular Graphs of Girth 8 and 12.» Can. J. Math. 18, 1091—1094, 1966.
4. Exoo, G. «Rectilinear Drawings of Famous Graphs» [Архівовано 24 червня 2021 у Wayback Machine.].
5. Pegg, E. T. and Exoo, G. «Crossing Number Graphs.» Mathematica J. 11, 2009.
6. Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
7. Balaban, A. T. «Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages.» Rev. Roumaine Math 18, 1033—1043, 1973.
8. Iofinova, M. E. and Ivanov, A. A. «Bi-Primitive Cubic Graphs.» In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123—134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137—152, 1985.)
9. Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), A census of semisymmetric cubic graphs on up to 768 vertices, Journal of Algebraic Combinatorics, 23: 255—294, doi:10.1007/s10801-006-7397-3.