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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Татта — Коксетера
Изображение
Назван в честь

Уильям Татт (англ.)
Гарольд Коксетер

Вершин

30

Рёбер

45

Диаметр

4

Обхват

8

Автоморфизмы

1440 (Aut(S6))

Хроматическое число

2

Хроматический индекс

3

Свойства

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

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

Является одним из тринадцати кубических дистанционно-регулярных графов[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.

Литература[править | править вики-текст]

  • H. S. M. Coxeter The chords of the non-ruled quadric in PG(3,3) // Canad. J. Math. — 1958. — Т. 10. — С. 484—488. — DOI:10.4153/CJM-1958-047-0.
  • 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.

Ссылки[править | править вики-текст]