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-клітки Татта:
Це єдиний граф з таким характеристичним поліномом; тому, 12-клітка Татта визначається своїм спектром.
Галерея
ред.-
Хроматичне число 12-клітки Татта дорівнює 2. -
Хроматичний індекс 12-клітки Татта дорівнює 3.
Примітки
ред.- ↑ а б в Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
- ↑ Weisstein, Eric W. Tutte 12-cage(англ.) на сайті Wolfram MathWorld.
- ↑ Benson, C. T. «Minimal Regular Graphs of Girth 8 and 12.» Can. J. Math. 18, 1091—1094, 1966.
- ↑ Exoo, G. «Rectilinear Drawings of Famous Graphs» [Архівовано 24 червня 2021 у Wayback Machine.].
- ↑ Pegg, E. T. and Exoo, G. «Crossing Number Graphs.» Mathematica J. 11, 2009.
- ↑ Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
- ↑ Balaban, A. T. «Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages.» Rev. Roumaine Math 18, 1033—1043, 1973.
- ↑ 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.)
- ↑ 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.