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

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

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

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-клітки Татта:

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

Галерея

Примітки

  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.