Панциклический граф

Циклы всех возможных длин в графе октаэдра , показывающие, что он панцикличен.

В математическом исследовании теории графов панциклический граф — это ориентированный граф или неориентированный граф , который содержит циклы всех возможных длин от трех до количества вершин в графе. Панциклические графы — это обобщение гамильтоновых графов , графов, которые имеют цикл максимально возможной длины.

Определения

Граф из n вершин G является панциклическим , если для любого $k$ в диапазоне $3\leq k\leq n\;,G$ содержит цикл длины $k$. Он является панциклическим по узлам или панциклическим по вершинам , если для каждой вершины v и каждого k в том же диапазоне он содержит цикл длины k , который содержит v . Аналогично, он является реберно-панциклическим , если для каждого ребра e и каждого k в том же диапазоне он содержит цикл длины k , содержащий e .

Двудольный граф не может быть панциклическим, поскольку он не содержит циклов нечетной длины, но его называют бипанциклическим, если он содержит циклы всех четных длин от 4 до n .

Планарные графы

Максимальный простым внешнепланарный граф — это граф, образованный многоугольником на плоскости путем триангуляции его внутренней части. Любой максимальный внешнепланарный граф является панциклическим, как можно показать по индукции. Внешняя грань графа представляет собой цикл из n вершин, и удаление любого треугольника, соединенного с остальной частью графа только одним ребром (листом дерева, образующим двойственный граф триангуляции), образует максимальный внешнепланарный граф на одном меньшее количество вершин, которое по индукции имеет циклы всех остальных длин. При более тщательном выборе треугольника для удаления тот же аргумент более убедительно показывает, что каждый максимальный внешнепланарный граф является панциклическим по узлам. То же самое справедливо для графов, которые имеют максимальный внешнепланарный охватывающий подграф , как, например, для графов-колес .

Максимальный планарный граф — это планарный граф, в котором все грани, даже внешняя грань, являются треугольниками. Максимальный планарный граф является панциклическим по узлам тогда и только тогда, когда он имеет гамильтонов цикл: если он не гамильтонов, он, конечно, не панцикличен, а если он гамильтонов, то внутренняя часть гамильтонова цикла образует максимальный внешнепланарный граф на тех же узлах, к которому можно применить предыдущий аргумент для максимальных внешнепланарных графов. Например, на иллюстрации показана панцикличность графа октаэдра , гамильтонова максимального плоского графа с шестью вершинами. Более строго, по тому же аргументу, если максимальный планарный граф имеет цикл длины k , у него есть циклы всех меньших длин.

Почти панциклический граф Халина с циклами любой длины до n, кроме длины 8.

Графы Халина — это плоские графы, сформированные из плоского рисунка дерева , не имеющего вершин второй степени, путем добавления к рисунку цикла, соединяющего все листья дерева. Графы Халина не обязательно панцикличны, но они почти панцикличны в том смысле, что отсутствует не более одной длины цикла. Длина недостающего цикла обязательно четная. Если ни одна из внутренних вершин графа Халина не имеет степени три, то он обязательно панцикличен.

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

Турниры

Турнир представляет собой ориентированный граф с одним направленным ребром между каждой парой вершин. Интуитивно понятно, что турнир можно использовать для моделирования спортивных соревнований по круговой системе , получая преимущество от победителя к проигравшему в каждой игре соревнования. Турнир называется сильно связным или сильным тогда и только тогда, когда его нельзя разбить на два непустых подмножества L и W проигравших и победителей, так что каждый участник в W побеждает каждого участника в L . Каждый сильный турнир панцикличен. и узлово-панциклический. Если турнир является регулярным (каждый участник имеет одинаковое количество побед и поражений, как и каждый другой участник), то он также является панциклическим; однако сильный турнир с четырьмя вершинами не может быть реберно-панциклическим.

Графы со многими ребрами

Теорема Мантеля утверждает, что любой неориентированный граф с n -вершинами, в котором не менее n ² /4 ребра и отсутствие кратных ребер или петель либо содержит треугольник, либо представляет собой полный двудольный граф K _{n /2, n /2} . Эту теорему можно усилить: любой неориентированный гамильтонов граф с по крайней мере n ² /4 ребра либо панцикличны, либо K _{n /2, n /2} .

Существуют n -вершинные гамильтоновы ориентированные графы с n ( n + 1)/2 − 3 ребрами, которые не являются панциклическими, но каждый гамильтонов ориентированный граф с не менее n ( n + 1)/2 − 1 ребром является панциклическим. Кроме того, каждый сильно связный ориентированный граф с n -вершинами, в котором каждая вершина имеет степень не ниже n (считая входящие и исходящие ребра вместе), является либо панциклическим, либо представляет собой полный двудольный ориентированный граф.

Полномочия графа

Для любого графа G его k- я степень G ^к определяется как граф на одном и том же множестве вершин, который имеет ребро между любыми двумя вершинами, расстояние которых в G не превышает k . Если G , 2-вершинно связна то по теореме Флейшнера ее квадрат G ² является гамильтоновым; это можно усилить, чтобы показать, что оно обязательно вершинно-панциклично. Более сильно, всякий раз, когда G ² гамильтонов, он также панцикличен.

Вычислительная сложность

NP -полна проверка того, является ли граф панциклическим, даже для частного случая 3-связных кубических графов , а также NP-полна для проверки того, является ли граф панциклическим по узлам, даже для частного случая многогранных графов. . Также NP-полна проверка того, является ли квадрат графа гамильтоновым и, следовательно, является ли он панциклическим.

История

Панцикличность впервые исследовали в контексте турниров Харари и Мозер (1966) , Мун (1966) и Альспах (1967) . Концепция панцикличности была названа и распространена на неориентированные графы Бонди (1971) .

Ссылки

• Олспах, Брайан (1967), «Циклы каждой длины в регулярных турнирах» , Canadian Mathematical Bulletin , 10 (2): 283–286, doi : 10.4153/cmb-1967-028-6 .
• Бернхарт, Фрэнк; Кайнен, Пол К. (1979), «Толщина графа в книге», Журнал комбинаторной теории , серия B , 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 .
• Бонди, Дж. А. (1971), «Панциклические графы I», Журнал комбинаторной теории , серия B , 11 (1): 80–84, doi : 10.1016/0095-8956(71)90016-5 .
• Флейшнер, Х. (1976), «В квадрате графов гамильтоновость и панцикличность, гамильтонова связность и пансвязность являются эквивалентными понятиями», Monatshefte für Mathematik , 82 (2): 125–149, doi : 10.1007/BF01305995 , MR   0427135 .
• Хэггквист, Роланд; Томассен, Карстен (1976), «О панциклических орграфах», Журнал комбинаторной теории , серия B , 20 (1): 20–40, doi : 10.1016/0095-8956(76)90063-0 .
• Хакими, СЛ ; Шмейхель, EF (1979), «О количестве циклов длины k в максимальном плоском графе», Journal of Graph Theory , 3 : 69–86, doi : 10.1002/jgt.3190030108 .
• Харари, Фрэнк ; Мозер, Лео (1966), «Теория круговых турниров», American Mathematical Monthly , 73 (3): 231–246, doi : 10.2307/2315334 .
• Хелден, Гвидо (2007), Гамильтоновость максимальных плоских графов и плоских триангуляций (PDF) , диссертация, Rheinisch-Westfälische Technische Hochschule Aachen, заархивировано из оригинала (PDF) 18 июля 2011 г.
• Хоббс, Артур М. (1976), «Квадрат блока является панциклическим вершиной», Журнал комбинаторной теории , серия B, 20 (1): 1–4, doi : 10.1016/0095-8956(76)90061-7 , МР   0416980 .
• Ли, Мин-Чу; Корнейл, Дерек Г .; Мендельсон, Эрик (2000), «Панцикличность и NP-полнота в плоских графах», Discrete Applied Mathematics , 98 (3): 219–225, doi : 10.1016/S0166-218X(99)00163-8 .
• Малкевич, Джозеф (1971), «О длинах циклов в плоских графах», «Последние тенденции в теории графов» , «Конспекты лекций по математике», том. 186, Springer-Verlag, стр. 191–195, doi : 10.1007/BFb0059437 .
• Мун, JW (1966), «О подтурнирах турнира» , Canadian Mathematical Bulletin , 9 (3): 297–301, doi : 10.4153/CMB-1966-038-7 .
• Рандерат, Берт; Ширмейер, Инго; Тьюс, Майке; Фолькманн, Лутц (2002), «Вершинные панциклические графы», Discrete Applied Mathematics , 120 (1–3): 219–237, doi : 10.1016/S0166-218X(01)00292-X .
• Шмейхель, Эдвард; Митчем, Джон (1982), «Двудольные графы с циклами любой четной длины», Journal of Graph Theory , 6 (4): 429–439, doi : 10.1002/jgt.3190060407 .
• Сковроньска, Мирослава (1985), «Панцикличность графов Халина и их внешние сокращения», в Олспах, Брайан Р .; Годсил, Кристофер Д. (ред.), Циклы в графиках , Анналы дискретной математики, том. 27, Elsevier Science Publishers BV, стр. 179–194 .
• Underground, Полли (1978), «О графиках с квадратами Гамильтона», Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR   0522906 .

Внешние ссылки

• Вайсштейн, Эрик В. «Панциклический граф» . Математический мир .