12-клітка Татта або граф Бенсона, в теорії графів, є регулярним графом зі 126 вершинами і 189 ребрами, названий на честь Вільяма Татта.
12-Клітка Татта | |
---|---|
The Tutte 12-cage | |
Названо на честь | Вільям Татт |
(Вершин) | 126 |
(Ребер) | 189 |
(Радіус) | 6 |
(Діаметр) | 6 |
(Обхват) | 12 |
(Автоморфізм) | 12096 |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
Властивості | Кубічний Теорія графів Гамільтонів граф Напівсиметричний Двочастковий |
12-клітка Татта є унікальним клітинним графом (3-12) (послідовність A052453 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Він був відкритий Бенсоном у 1966 році. У цього графу хроматичне число дорівнює 2 (двочастковий), хроматичний індекс 3, обхват 12 (12-клітка) та його (діаметр) дорівнює 6. Цей граф має лише 170 схрещень, і Бенсон припустив, що це може бути найменший кубічний граф з таким числом схрещень.
Побудова
12-клітка Татта є кубічний Гамільтонів граф, тому його можна записати у LCF-нотації як [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17]
Як довели А. М. Коен і [en] з точністю до ізоморфізму існує рівно два узагальнених шестикутники порядку (2,2). Вони є розщепленням шестикутника Келі H(2) з дуальністю точка-відрізок. Очевидно, що обидва з них мають однакові графи інцидентності, який фактично ізоморфний 12-клітці Татта.
11-клітка Балабана може бути побудована шляхом усічення з 12-клітки Татта, видаляючи невелике дерево і пригнічуючи отримані вершини степеня два.
Алгебраїчні властивості
Група автоморфізмів 12-клітки Татта має порядок 12 096 і є напівпрямим добутком проективної спеціальної унітарної групи PSU(3,3) з циклічною групою Z/2Z. Вони діють транзитивно на його ребрах, але не на його вершинах, що робить його напівсиметричним графом, тобто регулярним графом, який є реберно-транзитивним, але не є вершинно-транзитивним. Фактично, група автоморфізмів Татта 12-клітки зберігає двоподільні частини і діє примітивно на кожній частині. Такі графи називаються бі-примітивними графами, і існує лише п'ять бі-примітивних кубічних графів; вони названі як графи Iofinova–Ivanov зі 110, 110, 126, 182, 506 і 990 вершинами.
Відомі всі кубічні напівсиметричні графи кількість вершин яких не перевищує 768. Згідно з Conder, Malnič, Marušič і Potočnik, 12-клітка Татта є єдиним кубічним напівсиметричним графом зі 126 вершинами і є п'ятим найменшим можливим кубічним напівсиметричним графом після графу Грея та графу Iofinova–Ivanov на 110 вершин, графу Любляни та графу на 120 вершин з обхватом 8.
Характеристичний поліном 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.)
- ; Malnič, Aleksander; ; 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
12 klitka Tatta abo graf Bensona v teoriyi grafiv ye regulyarnim grafom zi 126 vershinami i 189 rebrami nazvanij na chest Vilyama Tatta 12 Klitka TattaThe Tutte 12 cageNazvano na chestVilyam TattVershin126Reber189Radius6Diametr6Obhvat12Avtomorfizm12096Hromatichne chislo2Hromatichnij indeks3VlastivostiKubichnij Teoriya grafiv Gamiltoniv graf Napivsimetrichnij Dvochastkovij 12 klitka Tatta ye unikalnim klitinnim grafom 3 12 poslidovnist A052453 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Vin buv vidkritij Bensonom u 1966 roci U cogo grafu hromatichne chislo dorivnyuye 2 dvochastkovij hromatichnij indeks 3 obhvat 12 12 klitka ta jogo diametr dorivnyuye 6 Cej graf maye lishe 170 shreshen i Benson pripustiv sho ce mozhe buti najmenshij kubichnij graf z takim chislom shreshen Pobudova12 klitka Tatta ye kubichnij Gamiltoniv graf tomu jogo mozhna zapisati u LCF notaciyi yak 17 27 13 59 35 35 11 13 53 53 27 21 57 11 21 57 59 17 Yak doveli A M Koen i en z tochnistyu do izomorfizmu isnuye rivno dva uzagalnenih shestikutniki poryadku 2 2 Voni ye rozsheplennyam shestikutnika Keli H 2 z dualnistyu tochka vidrizok Ochevidno sho obidva z nih mayut odnakovi grafi incidentnosti yakij faktichno izomorfnij 12 klitci Tatta 11 klitka Balabana mozhe buti pobudovana shlyahom usichennya z 12 klitki Tatta vidalyayuchi nevelike derevo i prignichuyuchi otrimani vershini stepenya dva Algebrayichni vlastivostiGrupa avtomorfizmiv 12 klitki Tatta maye poryadok 12 096 i ye napivpryamim dobutkom proektivnoyi specialnoyi unitarnoyi grupi PSU 3 3 z ciklichnoyu grupoyu Z 2Z Voni diyut tranzitivno na jogo rebrah ale ne na jogo vershinah sho robit jogo napivsimetrichnim grafom tobto regulyarnim grafom yakij ye reberno tranzitivnim ale ne ye vershinno tranzitivnim Faktichno grupa avtomorfizmiv Tatta 12 klitki zberigaye dvopodilni chastini i diye primitivno na kozhnij chastini Taki grafi nazivayutsya bi primitivnimi grafami i isnuye lishe p yat bi primitivnih kubichnih grafiv voni nazvani yak grafi Iofinova Ivanov zi 110 110 126 182 506 i 990 vershinami Vidomi vsi kubichni napivsimetrichni grafi kilkist vershin yakih ne perevishuye 768 Zgidno z Conder Malnic Marusic i Potocnik 12 klitka Tatta ye yedinim kubichnim napivsimetrichnim grafom zi 126 vershinami i ye p yatim najmenshim mozhlivim kubichnim napivsimetrichnim grafom pislya grafu Greya ta grafu Iofinova Ivanov na 110 vershin grafu Lyublyani ta grafu na 120 vershin z obhvatom 8 Harakteristichnij polinom 12 klitki Tatta x 3 x 28 x 3 x 2 6 21 x 2 2 27 displaystyle x 3 x 28 x 3 x 2 6 21 x 2 2 27 Ce yedinij graf z takim harakteristichnim polinomom tomu 12 klitka Tatta viznachayetsya svoyim spektrom GalereyaHromatichne chislo 12 klitki Tatta dorivnyuye 2 Hromatichnij indeks 12 klitki Tatta dorivnyuye 3 PrimitkiGeoffrey Exoo amp Robert Jajcay Dynamic cage survey Electr J Combin 15 2008 Weisstein Eric W Tutte 12 cage angl na sajti 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 chervnya 2021 u 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 Malnic Aleksander Potocnik Primoz 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