Граф Хивуда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Хивуда
Изображение
Вершин

14

Рёбер

21

Радиус

3

Диаметр

3

Обхват

6

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

336 (PGL2(7))

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

2

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

3

Свойства

двудольный
кубический
клетка
дистанционно-транзитивный
дистанционно-регулярный
тороидальный
гамильтонов
симметричный

Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названый в честь Перси Джона Хивуда[en][1].

Комбинаторные свойства[править | править вики-текст]

Граф является кубическим и все циклы в графе содержат шесть и более рёбер. Любой меньший кубический граф содержит меньшие циклы, так что этот граф является (3,6)-клеткой, наименьшим кубическим графом с обхватом 6. Он является также дистанционно-транзитивным (смотрите список Фостера, а потому дистанционно-регулярным[2]. В графе Хивуда имеется 24 паросочетания, и во всех паросочетаниях рёбра, не входящие в паросочетание, образуют гамильтонов цикл. Например, рисунок показывает вершины графа, помещённые на окружность и образующие цикл, а диагонали внутри окружности образуют паросочетание. Если разделить рёбра цикла на два паросочетания, мы получим три совершенных паросочетания (то есть, 3-цветную раскраску рёбер) восемью различными способами[2]. Ввиду симметрии графа любые два совершенных паросочетания и любые два гамильтоновых цикла можно преобразовать из одного в другое[3].

В графе Хивуда 28 циклов, содержащих по шесть вершин. Каждый такой цикл не связен в точности с тремя другими 6-вершинными циклами. Среди этих трёх циклов каждый является симметрической разностью двух других. Граф, в котором, каждая вершина соответствует циклу из 6 вершин графа Хивуда, а дуги соответствуют несвязным парам — это граф Коксетера[4].

Геометрические и топологические свойства[править | править вики-текст]

Граф Хивуда является тороидальным графом. То есть, его можно вложить без пересечений в тор. Одно из вложений такого типа размещает вершины и рёбра графа в трёхмерном евклидовом пространстве в виде множества вершин и рёбер невыпуклдого многогранника с топологией тора, многогранника Силаши[en]. Граф назван в честь Перси Джона Хивуда[en], доказавшего в 1890, что для раскраски любого разбиения тора на многоугольники достаточно семи цветов[5][6]. Граф Хивуда образует разбиение тора на семь взаимно смежных областей, что показывает, что граница точна. Граф Хивуда является также графом Леви поверхности Фано[en], то есть графом, представляющим инцидентность точек и прямых в этой геометрии. В этой интерпретации, циклы длины 6 в графе Хивуда соответствуют треугольникам поверхности Фано. Граф Хивуда имеет число скрещиваний[en], равное 3, и является наименьшим кубическим графом с таким числом скрещиваний[7]. Вместе с графом Хивуда существует 8 различных графов порядка 14 с числом скрещиваний 3. Граф Хивуда является графом единичных расстояний — его можно вложить в плоскость так, что смежные вершины окажутся в точности на расстоянии единица, при этом никакие две вершины не попадут на одно и то же место плоскости и никакая точка не окажется внутри ребра. Однако у известных вложений этого типа отсутствует симметрия, присущая графу[8].

Алгебраические свойства[править | править вики-текст]

Группа автоморфизмов графа Хивуда изоморфна проективной линейной группой PGL2(7), группе порядка 336[9]. Он действует транзитивно на вершины, на рёбра и на дуги графа. Поэтому граф Хивуда является симметричным. Имеются автоморфизмы, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно списку Фостера граф Хивуда, обозначенный как F014A, является единственным кубическим графом с 14 вершинами[10][11]. Характеристический многочлен матрицы графа Хивуда — (x-3) (x+3) (x^2-2)^6. Спектр графа равен (-3)^1 (-\sqrt{2})^6 (\sqrt{2})^6 3^1 Это единственный граф с таким многочленом, который определяется спектром.

Хроматический многочлен графа равен:

\pi_G(z) = z(z-1)(z^{12} -20z^{11} + 190z^{10} - 1140z^9 + 4845z^8 - 15476z^7
+ 38340z^6 - 74587z^5 + 113433z^4 - 131700z^3+ 110794 z^2 - 60524z + 16161).

Галерея[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Weisstein, Eric W. Heawood Graph (англ.) на сайте Wolfram MathWorld.
  2. 1 2 Brouwer, Andries E. Heawood graph. Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989).
  3. 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. — В. 2. — Т. 92. — С. 395–404. — DOI:10.1016/j.jctb.2004.09.004.
  4. Italo J. Dejter From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. — DOI:10.1002/jgt.20597 — arΧiv1002.1960.
  5. Ezra Brown The many names of (7,3,1) // Mathematics Magazine. — 2002. — В. 2. — Т. 75. — С. 83–94. — DOI:10.2307/3219140
  6. P. J. Heawood Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322–339.
  7. последовательность A110507 в OEIS
  8. Eleven unit distance embeddings of the Heawood graph. — 2009. — arΧiv0912.5395.
  9. J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York: North Holland, 1976. — С. 237. — ISBN 0-444-19451-7.
  10. Royle, G. «Кубические симметричные графы (список Фостера).»
  11. Марстон Кондер[en] и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.