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

Подгамильтонов граф — это подграф планарного гамильтонова графа .

Определение

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

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

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

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

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

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

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

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

Примечания

, с. 198–218.
↑ , с. 35–46.
Например, в техническом отчёте 2003 года " от 29 августа 2017 на Wayback Machine ", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
↑ .
.
, с. 320–331.
, с. 171–184.
, с. 287–294.
, с. 835–837.
Разделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части ( ).
То есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины.

Литература

Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8 , вып. 2 . — С. 198–218 . — doi : .
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 : .
Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory . — 1979. — Т. 27 , вып. 3 . — С. 320–331 . — doi : .
Takao Nishizeki, Norishige Chiba,. Planar Graphs: Theory and Algorithms. — Courier Dover Publications, 2008. — С. 171–184. — (Dover Books on Mathematics). — ISBN 9780486466712 .
G. Cornuéjols, D. Naddef, W. R. Pulleyblank. Halin graphs and the travelling salesman problem // Mathematical Programming. — 1983. — Т. 26 , вып. 3 . — С. 287–294 . — doi : .
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 : .
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov. Planarity-Preserving Clustering and Embedding for Large Planar Graphs // Computational Geomenty. — Elsevier, 2003. — Вып. 24 .