Підгамільтонів граф — це підграф планарного гамільтонового графа.
Визначення Граф підгамільтонів, якщо є підграфом деякого іншого графа з тією ж множиною вершин, при цьому граф планарний і містить гамільтонів цикл. Щоб ці умови виконувалися, сам граф має бути планарним і, крім того, має бути можливість додати ребра зі збереженням планарності, щоб створити у розширеному графі цикл, який проходить усі вершини рівно по одному разу. Граф називають гамільтоновим розширенням графа .
Можна було б дати визначення підгамільтонового графа як підграфа гамільтонового графа без вимоги, що цей більший граф має ту ж множину вершин. Тобто в цьому альтернативному визначенні можна було б додавати вершини та ребра. Однак, якщо граф можна зробити гамільтоновим за допомогою додавання вершин і ребер, його можна зробити таким і без додавання вершин, тому ця додаткова свобода не змінює визначенняНаприклад, у технічному звіті 2003 року «Book embeddings of graphs and a theorem of Whitney», Пол Кайнен визначає підгамільтонові графи як підграфи планарних гамільтонових графів без обмеження множини вершин у розширеному графі, але пише, що «у визначенні підгамільтонового графа можна вимагати, що розширення здійснюється лише додаванням ребер» .
У підгамільтоновому графі цикл — це циклічна послідовність вершин, така, що додавання ребра в будь-яку пару вершин у послідовності не порушує планарності графа. Граф є підгамільтоновим тоді й лише тоді, коли він має підгамільтонів цикл.
Історія та застосування Клас підгамільтонових графів (але не назву класу) запропонували Бернгарт та Кайнен. Вони довели, що це точно ті графи, які мають дві сторінки в книжкових вкладеннях. Підгамільтонові графи та гамільтонові розширення використовують також у галузі візуалізації графів для задач вкладення графів у універсальну множину точок, одночасного вкладення кількох графів та пошарового малювання графа.
Пов'язані сімейства графів Деякі класи планарних графів обов'язково гамільтонові, тому й підгамільтонові. Сюди входять 4-вершинно-зв'язні графи та графи Халіна.
Будь-який планарний граф із найбільшим степенем, що не перевищує чотирьох, є підгамільтоновим, як і будь-який планарний граф без розділювальних трикутниківРозділювальний трикутник — це подграф, що містить три вершини і три ребра, видалення якого (разом із суміжними ребрами) призводить до розбиття графа на незв'язані частини .. Якщо ребра довільного планарного графа розбито на шляхи довжини дваТобто кожне ребро перетворено на два ребра шляхом поміщення на ребро вершини., граф, що вийшов, завжди підгамільтонів.
Примітки
Література