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

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

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

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

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

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

Герц, Дубі й Віге висловили гіпотезу, що будь-який гіпогамільтонів граф має обхват 5 або більше, але її спростував Томассен, який знайшов приклади з обхватом 3 і 4. Протягом деякого часу не було відомо, чи можуть гіпогамільтонові графи бути планарними, але нині відомі деякі приклади таких графівЗадачу про існування планарних гіпогамільтонових графів поставив як відкрите питання Вацлав Хватал і група у складі Хватала, Кларнера та Кнута обіцяла приз у розмірі 5 доларів тому, хто знайде такий граф . Томассен для пошуку планарних гіпогамільтонових графів з охопленням 3, 4 і 5 використав і показав, що існує нескінченно багато планарних гіпогамільтонових графів. і найменший із них має 40 вершин.Знайшли Джуянде, Мккей, Естерґард і Петтерссон , скориставшись комп'ютерним пошуком і . Раніше малі планарні гіпогамільтонові графи з 42, 57 і 48 вершинами знайшли Вінер і Арая , Гатцель і Замфіреску . Будь-який планарний гіпогамільтонів граф має щонайменше одну вершину тільки з трьома інцидентними ребрами.

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

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

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

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

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

Додаткові нескінченні сімейства дали Бонді, Доєн і ван Діст та Ґутт.

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

Узагальнення Теоретики вивчають також гіповирисовувані графи — графи, які містять гамільтонів шлях, але в яких будь-яку підмножину n − 1 вершин можна з'єднати шляхом. Аналогічні визначення гіпогамільтоновості та гіповирисовуваності деякі автори запропонували для орієнтованих графів.

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

Примітки

Література

. As cited by

Посилання