Підгамільтонів граф

Підгамільтонів граф — це підграф планарного гамільтонового графа^[1][2].

Визначення

Граф ${\displaystyle G}$ підгамільтонів, якщо ${\displaystyle G}$ є підграфом деякого іншого графа ${\displaystyle aug(G)}$ з тією ж множиною вершин, при цьому граф ${\displaystyle aug(G)}$ планарний і містить гамільтонів цикл. Щоб ці умови виконувалися, сам граф ${\displaystyle G}$ має бути планарним і, крім того, має бути можливість додати ребра зі збереженням планарності, щоб створити у розширеному графі цикл, який проходить усі вершини рівно по одному разу. Граф ${\displaystyle aug(G)}$ називають гамільтоновим розширенням графа ${\displaystyle G}$^[2].

Можна було б дати визначення підгамільтонового графа як підграфа гамільтонового графа без вимоги, що цей більший граф має ту ж множину вершин. Тобто в цьому альтернативному визначенні можна було б додавати вершини та ребра. Однак, якщо граф можна зробити гамільтоновим за допомогою додавання вершин і ребер, його можна зробити таким і без додавання вершин, тому ця додаткова свобода не змінює визначення^[3].

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

Історія та застосування

Клас підгамільтонових графів (але не назву класу) запропонували Бернгарт та Кайнен^[5]. Вони довели, що це точно ті графи, які мають дві сторінки в книжкових вкладеннях^[6]. Підгамільтонові графи та гамільтонові розширення використовують також у галузі візуалізації графів для задач вкладення графів у універсальну множину точок, одночасного вкладення кількох графів та пошарового малювання графа^[2].

Пов'язані сімейства графів

Деякі класи планарних графів обов'язково гамільтонові, тому й підгамільтонові. Сюди входять 4-вершинно-зв'язні графи^[7] та графи Халіна^[8].

Будь-який планарний граф із найбільшим степенем, що не перевищує чотирьох, є підгамільтоновим^[4], як і будь-який планарний граф без розділювальних трикутників^[9][10]. Якщо ребра довільного планарного графа розбито на шляхи довжини два^[11], граф, що вийшов, завжди підгамільтонів^[2].