Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug(G) с тем же множеством вершин, при этом граф aug(G) планарен и содержит гамильтонов цикл. Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug(G) называется гамильтоновым расширением графа G[2].
Можно было бы дать определение подгамильтонова графа как подграфа гамильтонова графа без требования, что этот больший граф имеет то же самое множество вершин. То есть в этом альтернативном определении можно было бы добавлять вершины и рёбра. Однако, если граф может быть сделан гамильтоновым с помощью добавления вершин и рёбер, его можно сделать таковым и без добавления вершин, так что эта дополнительная свобода не меняет определение[3]
В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл[4].
Любой планарный граф с максимальной степенью, не превосходящей четырёх, является подгамильтоновым[4], как и любой планарный граф без разделяющих треугольников[9][10].
Если рёбра произвольного планарного графа разбиты на пути длины два[11], получившийся граф всегда подгамильтонов[2].
↑Например, в техническом отчёте 2003 года "Book embeddings of graphs and a theorem of WhitneyАрхивная копия от 29 августа 2017 на Wayback Machine", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
↑Разделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части (Duncan, Goodrich, Kobourov 2003).
↑То есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины.
Литература
Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вып. 2. — С. 198–218. — doi:10.1137/0608018.
Emilio Di Giacomo, Giuseppe Liotta. WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010, Proceedings. — Berlin: Springer, 2010. — Т. 5942. — С. 35–46. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-11440-3_4.
G. Cornuéjols, D. Naddef, W. R. Pulleyblank. Halin graphs and the travelling salesman problem // Mathematical Programming. — 1983. — Т. 26, вып. 3. — С. 287–294. — doi:10.1007/BF02591867.
Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou. STACS. — 2014.
Paul C. Kainen, Shannon Overbay. Extension of a theorem of Whitney // Applied Mathematics Letters. — 2007. — Т. 20, вып. 7. — С. 835–837. — doi:10.1016/j.aml.2006.08.019.
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov. Planarity-Preserving Clustering and Embedding for Large Planar Graphs // Computational Geomenty. — Elsevier, 2003. — Вып. 24.
