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]

Як довели А. М. Коен і Жак Тітс з точністю до ізоморфізму існує рівно два узагальнених шестикутники порядку (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. Згідно з Сonder, 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».
  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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.