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

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

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

кубический
Симметричный
клетка
граф Мура
дистанционно-регулярный


дистанционно-транзитивный

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

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

Особенно простое комбинаторное построение графа Татта — Коксетера предложено Коксетером (Coxeter (b) 1958) и основывается на ранних работах Д. Д. Сильвестра (Sylvester 1844): образуем множество из шести элементов (например, это буквы 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 автоморфизмов графа, которые можно отождествить с автоморфизмами группы перестановок шести элементов (Coxeter (b) 1958). Внутренние автоморфизмы этой группы соответствуют перестановкам шести элементов, из которых определяем морфемы и наборы. Эти перестановки действуют на граф Татта — Коксетера путём перестановок вершин на каждой доле двудольного графа, сохранная каждую долю как множество. Вдобавок, внешние автоморфизмы группы перестановок переставляют местами доли двудольного графа. Как показал Коксетер, любой путь длиной до пяти рёбер графа Татта — Коксетера эквивалентен любому другому такому пути (то есть переводятся из одного в другой с помощью одного из таких автоморфизмов).

Галерея

Примечания
  1. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance — Regular Graphs. New York: Springer—Verlag, 1989.

Литература
  • 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:10.1017/S0305004100023720.
  • W. T. Tutte. The chords of the non-ruled quadric in PG(3,3) // Canad. J. Math. — 1958. — Т. 10. — С. 481—483. — doi:10.4153/CJM-1958-046-3.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.