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

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

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

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

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

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

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

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

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

${\displaystyle \pi _{G}(z)=z(z-1)(z^{12}-20z^{11}+190z^{10}-1140z^{9}+4845z^{8}-15476z^{7}}$

${\displaystyle +38340z^{6}-74587z^{5}+113433z^{4}-131700z^{3}+110794z^{2}-60524z+16161)}$ .

Галерея

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

Примечания