Граф Хивуда

Комбинаторные свойства

Граф является кубическим и все циклы в графе содержат шесть и более рёбер. Любой меньший кубический граф содержит меньшие циклы, так что этот граф является (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]. Характеристический многочлен матрицы графа Хивуда — . Спектр графа равен Это единственный граф с таким многочленом, который определяется спектром.

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

.

Галерея

Примечания

  1. Weisstein, Eric W. Heawood Graph (англ.) на сайте Wolfram MathWorld.
  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. Т. 92, вып. 2. С. 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. arXiv:1002.1960..
  5. Ezra Brown. The many names of (7,3,1) // Mathematics Magazine. — 2002. Т. 75, вып. 2. С. 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. Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. arXiv:0912.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. «Кубические симметричные графы (список Фостера).» Архивировано 20 июля 2008 года.
  11. Марстон Кондер и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.