Граф Хівуда

Граф є кубічним і всі цикли в графі містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є (3,6) -кліткою, найменшим кубічним графом з обхватом 6. Він є також дистанційно-транзитивним (дивіться список Фостера), а тому дистанційно-регулярним[2].У графі Хівуда мається 24 паросполучення, і у всіх паросполучень ребра, що не входять у паросполучення, утворюють гамільтонів цикл. Наприклад, малюнок показує вершини графу, поміщені на окружність і що утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами[2]. Зважаючи симетрії графу будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше[3].

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

Граф Хівуда є тороїдальним графом, тобто його можна вкласти без перетинів в тор. Одне з вкладень такого типу розміщує вершини і ребра графу в тривимірному евклідовому просторі у вигляді безлічі вершин і ребер неопуклого багатогранника з топологією тора, багатогранника Сілаші. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що для розмальовки будь-якого розбиття тора на багатокутники достатньо семи кольорів[5][6]. Граф Хівуда утворює розбиття тора на сім взаємно суміжних областей, що показує, що кордон точна. Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє инцидентность точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано,тобто графом, представленим iнцидентнiсть точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано. Граф Хівуда має число схрещувань рівне 3 і є найменшим кубічним графом з таким числом схрещувань[7]. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещувань 3. Граф Хівуда є графом одиничних відстаней — його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу[8].

Група автоморфізмів графу Хівуда ізоморфна проективної лінійної групою PGL2₂(7), групі порядку 336[9].Він діє транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є симетричним. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі списком Фостера граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами[10][11]. Характеристичний многочлен матриці графу Хівуда — ${\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.
• 
  Вкладення графу Хівуда в тор(показаний у вигляді квадрата з Періодичними граничними умовами), розділяє його на сім взаємно-суміжних областей

Примітки