Гіпогамільтонів граф

У теорії графів кажуть, що граф G гіпогамільтонів, якщо сам граф не має гамільтонового циклу, але будь-який граф, отриманий видаленням однієї вершини з G, є гамільтоновим.

Гіпогамільтонів граф, побудований Ліндгреном^[1]

Історія

Гіпогамільтонові графи першим вивчав 1963 року Сусельєр.^[2] Ліндгрен^[1] цитує Гаудіна, Герца й Россі (1964)^[3], а також Бусакера й Сааті (1965)^[4] як додатковий матеріал з цієї теми. Ще одна рання праця - стаття Герца, Дубі й Віге 1967 року.^[5]

Гретчел^[6] підсумував більшість робіт у цій галузі так:

Статті про ці графи ... зазвичай виявляють нові класи гіпогамільтонових і гіпонакреслюваних графів і показують, що для деяких n такі графи дійсно існують або що вони мають дивні й несподівані властивості.

Застосування

Гіпогамільтонові графи з'являються в цілочисельних розв'язках задачі комівояжера - гіпогамільтонові графи певного виду визначають фасети многогранника комівояжера, тіла, визначеного як опукла оболонка множини можливих розв'язків задачі комівояжера, і ці фасети можна використати для методів відсікальних площин^[en] під час розв'язування задачі за алгоритмом Гоморі.^[7][6][8] Гретчел зауважив,^[6] що обчислювальна складність визначення, чи є граф гіпогамільтоновим, хоча й не відома, мабуть, висока, що робить складним пошук фасет такого типу, за винятком фасет, визначених гіпогамільтоновими графами малих розмірів. На щастя, найменші графи приводять до найсильніших нерівностей для цієї задачі.^[9]

Поняття, близькі до гіпогамільтоновості, використовували Парк, Лім і Кім^[10] для вимірювання відмовостійкості мережевих топологій паралельних обчислень.

Властивості

Будь-який гіпогамільтонів граф має бути 3-вершинно-зв'язним, оскільки видалення будь-яких двох вершин залишає гамільтонів шлях, який зв'язний (у графі з видаленою однією вершиною існує гамільтонів цикл, а видалення другої вершини дає гамільтонів шлях). Існують гіпогамільтонові графи з n вершинами, в яких найбільший степінь вершини дорівнює n/2 і в яких приблизно n²/4 ребер.^[11]

Гіпогамільтонів граф Томассена (1974) з обхватом 3.

Герц, Дубі й Віге висловили гіпотезу^[5], що будь-який гіпогамільтонів граф має обхват 5 або більше, але її спростував Томассен,^[12] який знайшов приклади з обхватом 3 і 4. Протягом деякого часу не було відомо, чи можуть гіпогамільтонові графи бути планарними, але нині відомі деякі приклади таких графів^[13] і найменший із них має 40 вершин.^[14] Будь-який планарний гіпогамільтонів граф має щонайменше одну вершину тільки з трьома інцидентними ребрами.^[15]

Якщо 3-однорідний граф гамільтонів, його ребра можна пофарбувати в три кольори — використовуємо почергове розфарбовування ребер двома кольорами вздовж гамільтонового циклу (який, за лемою про рукостискання, має парну довжину), а третім кольором фарбуємо решту ребер. Таким чином, всі снарки, кубічні графи без мостів, які для розфарбовування ребер вимагають чотири кольори, повинні бути негамільтоновими, і багато відомих снарків гіпогамільтонові. Будь-який гіпокамільтонів снарк є бікритичним — видалення будь-яких двох вершин залишає підграф, ребра якого можна пофарбувати в три кольори.^[16][17] Триколірне розфарбування цього підграфа легко описати — після видалення вершини частина, що залишилася, містить гамільтонів цикл. Після видалення другої вершини цикл стає шляхом, ребра якого можна почергово пофарбувати двома кольорами. Ребра, що залишилися, утворюють паросполуку і всі ці ребра можна пофарбувати третім кольором.

Класи кольорів будь-якого 3-колірного розфарбування ребер 3-однорідного графа утворюють три паросполуки, таких, що кожне ребро належить рівно одній паросполуці. Гіпогамільтонові снарки не мають розкладів на паросполуки такого типу, але Геггквіст^[18] висловив гіпотезу, що ребра будь-якого гіпогамільтонового снарка можна використати для утворення шести паросполук, таких, що кожне ребро належить рівно двом паросполукам. Це спеціальний випадок гіпотези Бержа — Фулкерсона, що будь-який снарк має шість паросполук із такою властивістю.

Гіпогамільтонові графи не можуть бути двочастковими — у двочастковому графі вершину можна видалити з утворенням гамільтонового підграфа, тільки якщо вона належить до більшого з двох класів кольорів графа. Однак будь-який двочастковий граф зустрічається у вигляді породженого підграфа деякого гіпогамільтонового графа.^[19]

Приклади

Найменший гіпогамільтонів граф — це граф Петерсена.^[5] Загальніше, узагальнений граф Петерсена GP(n,2) є гіпогамільтоновим, якщо n = 5 (mod 6).^[20] Граф Петерсена є представником цієї побудови з n = 5.

Ліндгрен^[1] знайшов інший нескінченний клас гіпогамільтонових графів, у якому кількість вершин дорівнює 4 (mod 6). Побудова Ліндгрена складається з циклу довжини 3 (mod 6) та однієї центральної вершини. Центральна вершина з'єднана з кожною третьою вершиною циклу ребром, яке він називає спицею, а вершини на дві позиції від кінцевої вершини спиці з'єднуються одна з одною. Знову найменшим представником побудови Ліндгрена є граф Петерсена.

Додаткові нескінченні сімейства дали Бонді^[21], Доєн і ван Діст^[22] та Ґутт.^[23]

Перелік

Вацлав Хватал 1973 року довів, що для всіх досить великих n існує гіпогамільтонів граф із n вершинами. Якщо взяти до уваги подальші відкриття,^[24][22] «досить велика кількість» тепер відома, так що такі графи існують для всіх n ≥ 18. Повний список гіпогамільтонових графів із не більше ніж 17 вершинами відомий^[25] — це граф Петерсена з 10 вершинами, графи з 13 і 15 вершинами, які за допомогою комп'ютерного пошуку знайшов Герц,^[26] і чотири графи з 16 вершинами. Існує щонайменше тринадцять гіпогамільтонових графів із 18 вершинами. При застосуванні тригерного методу Хватала^[27] до графа Петерсена і снарка «квітка» можна показати, що кількість гіпогамільтонових графів, конкретніше, кількість гіпогамільтонових снарків, зростає як експонента від кількості вершин.^[28][29]

Узагальнення

Теоретики вивчають також гіповирисовувані графи — графи, які містять гамільтонів шлях, але в яких будь-яку підмножину n − 1 вершин можна з'єднати шляхом.^{[30][31][32][24]} Аналогічні визначення гіпогамільтоновості та гіповирисовуваності деякі автори запропонували для орієнтованих графів.^{[33][34][35][15]}

Еквівалентне визначення гіпогамільтонових графів — що їх найдовші цикли мають довжину n − 1 і що перетин усіх найдовших циклів порожній. Менке і Замфіреску^[36] досліджували графи з властивістю, що перетин найдовших циклів порожній, але в яких довжина таких циклів менша від n − 1. Герц^[26] визначив циклованість графа як найбільше число k таке, що будь-які k вершин належать циклу. Гіпогамільтонові графи — це точно графи, які мають циклованість n − 1. Подібно Парк, Лім і Кім^[10] визначили граф як ƒ-стійко негамільтонів, якщо видалення щонайбільше ƒ вершин дає гамільтонів підграф. Шауерте та Замфіреску^[37] вивчали графи з циклованістю n − 2.