Граф Татта — Коксетера (также 8-клетка Татта ) — 3- регулярный граф с 30 вершинами и 45 рёбрами. Единственный наименьший кубический граф с обхватом 8, является клеткой и графом Мура . Двудольный и может быть построен как граф Леви обобщённого четырёхугольника W ₂ (известного как конфигурация Кремоны — Ричмонда ). Назван в честь Уильяма Томаса Татта и Гарольда Коксетера . Найден Уильямом Таттом ( ), но его связь с геометрической комбинацией исследована обоими авторами в паре совместных статей ( , ).

Является одним из тринадцати кубических дистанционно-регулярных графов .

Двойки, наборы и автоморфизмы

Особенно простое комбинаторное построение графа Татта — Коксетера предложено Коксетером ( ) и основывается на ранних работах Д. Д. Сильвестра ( ): образуем множество из шести элементов (например, это буквы a, b, c, d, e, f); Сильвестр определил двойки как 15 неупорядоченных пар элементов: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, or ef. Он также определил наборы — разбиения элементов на три двойки: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, be, df); (ac, bf, de); (ad, bc, ef); (ad, be, cf); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Каждый набор содержит 3 двойки, и каждая двойка принадлежит трём наборам. Граф Татта — Коксетера можно рассматривать как граф, в котором каждая вершина соответствует двойке, а также набору двоек — по вершине для каждого набора, и рёбра соединяют каждый набор с тремя двойками, содержащихся в нём.

Основываясь на этом построении, Коксетер показал, что граф Татта — Коксетера является симметричным . Он имеет 1440 автоморфизмов графа , которые можно отождествить с автоморфизмами группы перестановок шести элементов ( ). Внутренние автоморфизмы этой группы соответствуют перестановкам шести элементов, из которых определяем морфемы и наборы. Эти перестановки действуют на граф Татта — Коксетера путём перестановок вершин на каждой доле двудольного графа, сохранная каждую долю как множество. Вдобавок, (англ.) ( группы перестановок переставляют местами доли двудольного графа. Как показал Коксетер, любой путь длиной до пяти рёбер графа Татта — Коксетера эквивалентен любому другому такому пути (то есть переводятся из одного в другой с помощью одного из таких автоморфизмов).

Галерея

• 
  Число пересечений графа Татта — Коксетера равно 13.
• 
  Хроматическое число графа Татта — Коксетера равно 2.
• 
  хроматический индекс графа Татта — Коксетера равен 3.

Примечания

Литература

• H. S. M. Coxeter. // Canad. J. Math. — 1958. — Т. 10 . — С. 484—488 . — doi : .

• H. S. M. Coxeter. Twelve points in PG(5,3) with 95040 self-transformations // Proceedings of the Royal Society A. — 1958. — Т. 247 , вып. 1250 . — С. 279—293 . — doi : . — JSTOR .

• J. J. Sylvester. Elementary researches in the analysis of combinatorial aggregation // The Philos. Mag., Series 3. — 1844. — Т. 24 . — С. 285—295 .

• W. T. Tutte. A family of cubical graphs // Proc. Cambridge Philos. Soc. — 1947. — Т. 43 , вып. 04 . — С. 459—474 . — doi : .

• W. T. Tutte. // Canad. J. Math. — 1958. — Т. 10 . — С. 481—483 . — doi : .

Ссылки

• François Labelle. (неопр.) . Дата обращения: 15 февраля 2014. 9 апреля 2009 года.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Exoo, G. «Rectilinear Drawings of Famous Graphs.» от 24 июня 2021 на Wayback Machine