12-клітка Татта
Шаблон:Граф 12-клітка Татта або граф Бенсона[1], в теорії графів, є регулярним графом зі 126 вершинами і 189 ребрами, названий на честь Вільяма Татта.[2]
12-клітка Татта є унікальним клітинним графом (3-12) (Шаблон: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. Згідно з Conder, Malnič, Marušič і Potočnik, 12-клітка Татта є єдиним кубічним напівсиметричним графом зі 126 вершинами і є п'ятим найменшим можливим кубічним напівсиметричним графом після графу Грея та графу Iofinova–Ivanov на 110 вершин, графу Любляни та графу на 120 вершин з обхватом 8.[9]
Характеристичний поліном 12-клітки Татта:
Це єдиний граф з таким характеристичним поліномом; тому, 12-клітка Татта визначається своїм спектром.
Галерея
-
Хроматичне число 12-клітки Татта дорівнює 2. -
Хроматичний індекс 12-клітки Татта дорівнює 3.
Примітки
- ↑ 1,0 1,1 1,2 Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
- ↑ Шаблон: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» Шаблон:Webarchive.
- ↑ 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.)
- ↑ Шаблон:Citation.