Граф Татта — Коксетера

У математичній області теорії графів, граф Татта — Коксетера являє собою 3-регулярний граф з 30 вершинами і 45 ребрами. Як єдиний найменший кубічний граф обхвату 8, він є клітиною і графом Мура. Також це двочастковий граф і він може бути побудований як граф Леві узагальненого чотирикутника W₂ (відомий як конфігурація Кремони — Річмонда. Граф був названий на честь Вільяма Томаса Татта і Х. С. М. Коксетера; був відкритий Таттом (1947), але його зв'язок з геометричними конфігураціями був досліджений обома авторами спільно, результати викладені в опублікованих статтях (Татт 1958; Кокстер 1958).

Граф Татта — Корсетера
Названо на честь	Вільям Татт Гарольд Коксетер
Вершин	30
Ребер	45
Радіус	4
Діаметр	4
Обхват	8
Автоморфізм	1440 (Aut(S6))
Хроматичне число	2
Хроматичний індекс	3
Число черг	2
Властивості	кубічний граф симетричний граф клітка граф Мура дистанційно-регулярний граф дистанційно-транзитивний граф двочастковий

Всі кубічні дистанційно-регулярні графи відомі.^[1] Граф Татта — Кокстера є одним з 13 таких графів.

Конструкції і автоморфізм

Особливо проста комбінаторна побудова графа Татта — Коксетера можлива завдяки роботі Коксетера (1958b), яка заснована на роботі Сильвестра (1844). У сучасній термінології, візьмемо повний граф на 6 вершин K₆. Він має 15 ребер, а також 15 парувань. Кожна вершина графа Татта — Коксетера відповідає ребру або паруванню з K₆, і кожне ребро графа Татта — Коксетера пов'язує узгодження K₆ до кожного з трьох складових ребер.

На основі цієї конструкції, Коксетер показав, що граф Татта — Коксетера — симетричний граф; він має групу з 1440 автоморфізмів, які можуть бути ідентифіковані за допомогою автоморфізмів групи перестановок на шести елементах (Коксетер, 1958b). Внутрішні автоморфізми^[en] цієї групи відповідають перестановці шести вершин графа specification; ці перестановки діють на граф Татта — Коксетера перестановкою вершин на кожній стороні його поділу на дві частини, зберігаючи при цьому кожну з двох сторін фіксованою у вигляді набору. Крім того, зовнішні автоморфізми групи^[en] перестановок міняють одну сторону двочасткового графа на іншу. Як показав Коксетер, будь-який шлях до п'яти ребер в графі Татта — Коксетера еквівалентний будь-якому іншому такому шляху на один такий автоморфізм.

Галерея

• 
  Хроматичне число графа Татта - Корсетера дорівнює 2.
• 
  Хроматичний індекс графа Татта - Корсетера дорівнює 3.