Субгамильтонов граф - Subhamiltonian graph - Wikipedia

В теория графов и рисунок графика, а субгамильтонов граф это подграф из планарный Гамильтонов граф.[1][2]

Определение

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

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

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

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

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

Связанные классы графов

Некоторые классы планарных графов обязательно гамильтоновы, а значит, и субгамильтоновы; к ним относятся 4-связные плоские графы[6] и Графики Халина.[7]

Каждый планарный граф с максимальная степень максимум четыре - субгамильтоновы,[4] как и любой плоский граф без разделяющих треугольников.[8]Если ребра произвольного плоского графа равны подразделяется на пути длины два, результирующий разбитый граф всегда будет субгамильтоновым.[2]

Рекомендации

  1. ^ Хит, Ленвуд С. (1987), "Вложение внешнепланарных графов в небольшие книги", Журнал SIAM по алгебраическим и дискретным методам, 8 (2): 198–218, Дои:10.1137/0608018, МИСТЕР  0881181.
  2. ^ а б c d Ди Джакомо, Эмилио; Лиотта, Джузеппе (2010), "Проблема гамильтонова увеличения и ее приложения к рисованию графов", WALCOM: Алгоритмы и вычисления, 4-й международный семинар, WALCOM 2010, Дакка, Бангладеш, 10-12 февраля 2010 г., Труды, Конспект лекций по информатике, 5942, Берлин: Springer, стр. 35–46, Дои:10.1007/978-3-642-11440-3_4, МИСТЕР  2749626.
  3. ^ Например, в техническом отчете за 2003 год "Книжные вложения графов и теорема Уитни ", Пол Кайнен определяет субгамильтоновы графы как подграфы плоских гамильтоновых графов без ограничения на набор вершин увеличения, но пишет, что «в определении субгамильтонова графа можно потребовать, чтобы расширение включало только новые ребра».
  4. ^ а б Бекос, Майкл А .; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2014), "Двухстраничные книжные вложения 4-плоских графов", STACS, arXiv:1401.0684, Bibcode:2014arXiv1401.0684B.
  5. ^ Bernhart, Frank R .; Кайнен, Пол К. (1979), «Книжная толщина графа», Журнал комбинаторной теории, Серия B, 27 (3): 320–331, Дои:10.1016/0095-8956(79)90021-2.
  6. ^ Нисизэки, Такао; Чиба, Norishige (2008), "Глава 10. Гамильтоновы циклы", Плоские графы: теория и алгоритмы, Dover Books on Mathematics, Courier Dover Publications, стр. 171–184, ISBN  9780486466712.
  7. ^ Корнежоль, Г.; Наддеф, Д .; Pulleyblank, W. R. (1983), "Графы Халина и проблема коммивояжера", Математическое программирование, 26 (3): 287–294, Дои:10.1007 / BF02591867.
  8. ^ Kainen, Paul C .; Overbay, Шеннон (2007), "Расширение теоремы Уитни", Письма по прикладной математике, 20 (7): 835–837, Дои:10.1016 / j.aml.2006.08.019, МИСТЕР  2314718.