Граф Хівуда

Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. Ви можете допомогти вдосконалити цю статтю, погодивши її із чинними мовними стандартами.

Граф Хівуда
Названо на честь	Персі Джон Хівуд
Вершин	14
Ребер	21
Радіус	3
Діаметр	3
Обхват	6
Автоморфізм	336 (PGL2(7))
Хроматичне число	2
Хроматичний індекс	3
Спектр	${\displaystyle (-3)^{1}(-{\sqrt {2}})^{6}({\sqrt {2}})^{6}3^{1}}$
Число черг	2
Властивості	Двочастковий Кубічний дистанційно-транзитивний дистанційно-регулярний тороїдальний гамільтонів Симетричний

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

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

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

Граф Хівуда є тороїдальним графом, тобто його можна відобразити без перетинів на поверхні тора. Як результат утворюється регулярна карта {6,3}_2,1 з 7 гексагональними поверхнями. Кожна поверхня мапи суміжна до кожної іншої, а отже карта потребує 7 кольорів. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що не існує карти для тора яка потребує більше 7, а отже карта є максимальною.^[5][6]

Ця карта також може бути вірно реалізована як многогранник Сілашші, єдиний відомий полігон, окрім тетраедра, в якому кожна пара граней є сусідніми.

Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано, тобто графом, представленим інцидентним точкам і прямих в цій геометрії. У цій інтерпретації цикли довжини 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)}$.

• 
  Багатогранник Сілаші^[ru].
• 
  Граф Хівуда має число схрещень 3.
• 
  Хроматичний індекс графу Хівуда дорівнює 3.
• 
  Хроматичне число графу Хівуда дорівнює 2.
• 
  Вкладення графу Хівуда в тор(показаний у вигляді квадрата з Періодичними граничними умовами^[en]), розділяє його на сім взаємно-суміжних областей

Примітки