Граф Хивуда
Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названый в честь Перси Джона Хивуда[1].
Граф Хивуда | |
---|---|
Назван в честь | Перси Джон Хивуд |
Вершин | 14 |
Рёбер | 21 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 6 |
Автоморфизмы | 336 (PGL2(7)) |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Свойства |
двудольный кубический клетка дистанционно-транзитивный дистанционно-регулярный тороидальный гамильтонов симметричный |
Медиафайлы на Викискладе |
Комбинаторные свойства
Граф является кубическим и все циклы в графе содержат шесть и более рёбер. Любой меньший кубический граф содержит меньшие циклы, так что этот граф является (3,6)-клеткой, наименьшим кубическим графом с обхватом 6. Он является также дистанционно-транзитивным (смотрите список Фостера), а потому дистанционно-регулярным[2]. В графе Хивуда имеется 24 паросочетания, и во всех паросочетаниях рёбра, не входящие в паросочетание, образуют гамильтонов цикл. Например, рисунок показывает вершины графа, помещённые на окружность и образующие цикл, а диагонали внутри окружности образуют паросочетание. Если разделить рёбра цикла на два паросочетания, мы получим три совершенных паросочетания (то есть, 3-цветную раскраску рёбер) восемью различными способами[2]. Ввиду симметрии графа любые два совершенных паросочетания и любые два гамильтоновых цикла можно преобразовать из одного в другое[3].
В графе Хивуда 28 циклов, содержащих по шесть вершин. Каждый такой цикл не связан в точности с тремя другими 6-вершинными циклами. Среди этих трёх циклов каждый является симметрической разностью двух других. Граф в котором каждая вершина соответствует циклу из 6 вершин графа Хивуда, а дуги соответствуют несвязным парам — это граф Коксетера[4].
Геометрические и топологические свойства
Граф Хивуда является тороидальным графом, то есть его можно вложить без пересечений в тор. Одно из вложений такого типа размещает вершины и рёбра графа в трёхмерном евклидовом пространстве в виде множества вершин и рёбер невыпуклого многогранника с топологией тора, многогранника Силаши. Граф назван в честь Перси Джона Хивуда, доказавшего в 1890 году, что для раскраски любого разбиения тора на многоугольники достаточно семи цветов[5][6]. Граф Хивуда образует разбиение тора на семь взаимно смежных областей, что показывает, что граница точна. Граф Хивуда является также графом Леви плоскостью Фано, то есть графом, представляющим инцидентность точек и прямых в этой геометрии. В этой интерпретации циклы длины 6 в графе Хивуда соответствуют треугольникам поверхности Фано. Граф Хивуда имеет число скрещиваний равное 3 и является наименьшим кубическим графом с таким числом скрещиваний[7]. Вместе с графом Хивуда существует 8 различных графов порядка 14 с числом скрещиваний 3. Граф Хивуда является графом единичных расстояний — его можно вложить в плоскость так, что смежные вершины окажутся в точности на расстоянии единица, при этом никакие две вершины не попадут на одно и то же место плоскости и никакая точка не окажется внутри ребра. Однако у известных вложений этого типа отсутствует симметрия, присущая графу[8].
Алгебраические свойства
Группа автоморфизмов графа Хивуда изоморфна проективной линейной группе PGL2(7), группе порядка 336[9]. Он действует транзитивно на вершины, на рёбра и на дуги графа, поэтому граф Хивуда является симметричным. Имеются автоморфизмы, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно списку Фостера граф Хивуда, обозначенный как F014A, является единственным кубическим графом с 14 вершинами[10][11]. Характеристический многочлен матрицы графа Хивуда — . Спектр графа равен Это единственный граф с таким многочленом, который определяется спектром.
Хроматический многочлен графа равен:
-
- .
Галерея
- Граф Хивуда имеет число скрещиваний 3.
- Хроматический индекс графа Хивуда равен 3.
- Хроматическое число графа Хивуда равно 2.
- Вложение графа Хивуда в тор (показан в виде квадрата с периодическими граничными условиями), разделяющий его на семь взаимно-смежных областей
Примечания
- Weisstein, Eric W. Heawood Graph (англ.) на сайте Wolfram MathWorld.
- Brouwer, Andries E. Heawood graph . Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989).
- M. Abreu, R. E. L. Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Graphs and digraphs with all 2-factors isomorphic // Journal of Combinatorial Theory. — 2004. — Т. 92, вып. 2. — С. 395—404. — doi:10.1016/j.jctb.2004.09.004..
- Italo J. Dejter. From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. — doi:10.1002/jgt.20597. — arXiv:1002.1960..
- Ezra Brown. The many names of (7,3,1) // Mathematics Magazine. — 2002. — Т. 75, вып. 2. — С. 83—94. — doi:10.2307/3219140. — .
- P. J. Heawood. Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322—339.
- последовательность A110507 в OEIS
- Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. — arXiv:0912.5395..
- J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York: North Holland, 1976. — С. 237. — ISBN 0-444-19451-7.
- Royle, G. «Кубические симметричные графы (список Фостера).» Архивировано 20 июля 2008 года.
- Марстон Кондер и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.