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

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

Определение

Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug(G) с тем же множеством вершин, при этом граф aug(G) планарен и содержит гамильтонов цикл. Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug(G) называется гамильтоновым расширением графа G^[2].

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

В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл^[4].

История и приложения

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

Связанные семейства графов

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

Любой планарный граф с максимальной степенью, не превосходящей четырёх, является подгамильтоновым^[4], как и любой планарный граф без разделяющих треугольников^[9][10]. Если рёбра произвольного планарного графа разбиты на пути длины два^[11], получившийся граф всегда подгамильтонов^[2].