В математической области теории графов граф Хивуда — неориентированный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда . [1]
Граф кубический , и все циклы в графе имеют шесть или более ребер. Каждый меньший кубический граф имеет более короткие циклы, поэтому этот граф является 6- клеткой , наименьшим кубическим графом обхвата 6. Это дистанционно-транзитивный граф (см. перепись Фостера ) и, следовательно, дистанционно-регулярный . [2]
В графе Хивуда существует 24 совершенных паросочетания ; для каждого паросочетания множество ребер, не входящих в паросочетание, образует гамильтонов цикл . Например, на рисунке показаны вершины графа, размещенные на цикле, с внутренними диагоналями цикла, образующими паросочетание. Разделив ребра цикла на два паросочетания, мы можем разбить граф Хивуда на три совершенных паросочетания (то есть раскрасить его ребра в 3 цвета ) восемью различными способами. [2] Каждые два совершенных паросочетания и каждые два гамильтоновых цикла можно преобразовать друг в друга с помощью симметрии графа. [3]
В графе Хивуда имеется 28 циклов с шестью вершинами. Каждый цикл из 6 вершин не пересекается ровно с тремя другими циклами из 6 вершин; среди этих трех циклов из 6 вершин каждый является симметричной разностью двух других. Граф с одним узлом на цикл из 6 вершин и одним ребром для каждой непересекающейся пары циклов из 6 вершин — это граф Коксетера . [4]
Граф Хивуда является тороидальным графом ; то есть он может быть вложен без пересечений в тор . Результатом является регулярная карта {6,3} 2,1 с 7 шестиугольными гранями. [5] Каждая грань карты смежна с каждой другой гранью, таким образом, в результате раскраска карты требует 7 цветов. Карта и граф были открыты Перси Джоном Хивудом в 1890 году, который доказал, что никакая карта на торе не может потребовать более семи цветов, и, таким образом, эта карта является максимальной. [6] [7]
Карту можно точно реализовать как многогранник Силасси [8], единственный известный многогранник, помимо тетраэдра , у которого каждая пара граней смежна.
Граф Хивуда — это граф Леви плоскости Фано , [5] граф, представляющий инцидентности между точками и прямыми в этой геометрии. При такой интерпретации 6-циклы в графе Хивуда соответствуют треугольникам в плоскости Фано. Также граф Хивуда — это здание Титса группы SL 3 (F 2 ) .
Граф Хивуда имеет число пересечений 3 и является наименьшим кубическим графом с этим числом пересечений (последовательность A110507 в OEIS ). Включая граф Хивуда, существует 8 различных графов порядка 14 с числом пересечений 3.
Граф Хивуда является наименьшим кубическим графом с инвариантом графа Колина де Вердьера μ = 6. [ 9]
Граф Хивуда является графом единичных расстояний : его можно встроить в плоскость таким образом, чтобы соседние вершины находились на расстоянии точно в единицу друг от друга, при этом никакие две вершины не вложены в одну и ту же точку, и никакая вершина не вложена в точку внутри ребра. [10]
Группа автоморфизмов графа Хивуда изоморфна проективной линейной группе PGL 2 (7), группе порядка 336. [11] Она действует транзитивно на вершинах, ребрах и дугах графа. Следовательно, граф Хивуда является симметричным графом . Он имеет автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Более того, граф Хивуда является 4-дуго-транзитивным . [12] Согласно переписи Фостера , граф Хивуда, обозначенный как F014A, является единственным кубическим симметричным графом на 14 вершинах. [13] [14]
Он имеет толщину книги 3 и номер очереди 2. [15]
Характеристический многочлен графа Хивуда равен . Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром.
