Граф Хивуда

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

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

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

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

Геометрические и топологические свойства

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

Алгебраические свойства

Группа автоморфизмов графа Хивуда изоморфна проективной линейной группе PGL₂(7), группе порядка 336. Он действует транзитивно на вершины, на рёбра и на дуги графа, поэтому граф Хивуда является симметричным. Имеются автоморфизмы, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно списку Фостера граф Хивуда, обозначенный как F014A, является единственным кубическим графом с 14 вершинами. Характеристический многочлен матрицы графа Хивуда — $(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+110794z^2-60524z+16161)$.

Галерея

• 
  Многогранник Силаши.
• 
  Граф Хивуда имеет число скрещиваний 3.
• 
  Хроматический индекс графа Хивуда равен 3.
• 
  Хроматическое число графа Хивуда равно 2.
• 
  Вложение графа Хивуда в тор (показан в виде квадрата с Шаблон:Не переведено 5), разделяющий его на семь взаимно-смежных областей