Граф Татта-Коксетера: кубический граф с 30 вершинами, минимальный обхват 8. Свойства, конструкция (граф Леви обобщенного четырехугольника W2) и история открытия.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В математической области теории графов граф Тутте — Коксетера, или восьмиклетка Тутте, или граф Кремона — Ричмонда — это 3-регулярный граф с 30 вершинами и 45 ребрами. Являясь единственным наименьшим кубическим графом с длиной окружности 8, он представляет собой клетку и граф Мура. Он является двудольным и может быть построен как граф Леви обобщённого четырехугольника W2 (известного как конфигурация Кремона — Ричмонда). Граф назван в честь Уильяма Томаса Тутте и Х. С. М. Коксетера; он был открыт Тутте в 1947 году, но связь с геометрическими конфигурациями была исследована обоими авторами в паре совместно опубликованных статей (Tutte, 1958; Coxeter, 1958a). Все кубические расстояние-регулярные графы известны. Граф Тутте — Коксетера — один из 13 таких графов. Его число пересечений равно 13, толщина книги — 3, а число очередей — 2.
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight cage or Cremona–Richmond graph is a 3 regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle W2 (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a). All the cubic distance regular graphs are known. The Tutte–Coxeter is one of the 13 such graphs. It has crossing number 13, book thickness 3 and queue number 2.
Конструкции и автоморфизмы
Граф Тютте — Коксетера — это двудольный граф Леви, соединяющий 15 полных соответствий 6-вершинного полного графа K6 с его 15 ребрами, как описано Коксетером (1958b) на основе работы Сильвестра (1844). Каждая вершина соответствует ребру или полному соответствию, а соединенные вершины представляют структуру инцидентности между ребрами и соответствиями. На основе этой конструкции Коксетер показал, что граф Тютте — Коксетера является симметричным графом; он имеет группу из 1440 автоморфизмов, которые можно отождествить с автоморфизмами группы перестановок на шести элементах (Коксетер 1958b). Внутренние автоморфизмы этой группы соответствуют перестановкам шести вершин графа K6; эти перестановки действуют на граф Тютте — Коксетера, переставляя вершины на каждой стороне его двудольности, при этом сохраняя каждую из двух сторон фиксированной как множество. Кроме того, внешние автоморфизмы группы перестановок меняют местами одну сторону двудольности с другой. Как показал Коксетер, любой путь длиной до пяти ребер в графе Тютте — Коксетера эквивалентен любому другому такому пути одним из этих автоморфизмов.
The Tutte–Coxeter graph is the bipartite Levi graph connecting the 15 perfect matchings of a 6 vertex complete graph K6 to its 15 edges, as described by Coxeter (1958b), based on work by Sylvester (1844). Each vertex corresponds to an edge or a perfect matching, and connected vertices represent the incidence structure between edges and matchings. Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph; it has a group of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six vertices of the K6 graph; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the outer automorphisms of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte–Coxeter graph is equivalent to any other such path by one such automorphism.