Панциклічний граф
Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа[1]. Панциклічні графи є узагальненням гамільтонових графів, графів, які мають цикли найбільшої можливої довжини.
Граф з вершинами є панциклічним, якщо для будь-якого в межах граф містить цикл довжини [1]. Граф є вершинно панциклічним, якщо для будь-якої вершини і будь-якого в тих самих межах граф містить цикл довжини , що містить вершину [2]. Схожим чином граф є реберно панциклічним, якщо для будь-якого ребра і для будь-якого в тих самих межах він містить цикл довжини , що містить ребро [2].
Двочастинний граф не може бути панциклічним, оскільки він не містить циклів будь-якої непарної довжини, але кажуть, що граф є біпанциклічним, якщо він містить цикли всіх парних довжин від 4 до [3].
Максимальний зовніпланарний граф — це граф, утворений із простого многокутника на площині шляхом тріангуляції його внутрішності. Будь-який максимальний зовніпланарний граф є панциклічним, що можна показати індукцією. Зовнішня грань графа є циклом з n вершинами, а видалення будь-якого трикутника, з'єднаного із рештою графа тільки одним ребром (листок дерева, яке утворює двоїстий граф тріангуляції), утворює максимальний зовніпланарний граф з на одиницю меншим числом вершин, а за індукційним припущенням цей граф має всі цикли всіх довжин, що залишилися. Якщо приділяти більше уваги вибору трикутника для видалення, то ті самі аргументи показують строгіший результат, що будь-який максимальний зовніпланарний граф є вершинно панциклічним[4]. Те ж саме істинне для графів, які мають максимальний зовніпланарний граф як кістяковий підграф, зокрема, для колеса.
Максимальний планарний граф — це планарний граф, у якому всі грані, включно із зовнішньою, є трикутниками. Максимальний планарний граф є вершинно панциклічним тоді й лише тоді, коли він містить гамільтонів цикл[5] — якщо він не гамільтонів, він безумовно не панциклічний, а якщо він гамільтонів, то внутрішність гамильтонового циклу утворює зовнішню межу максимального зовнішпланарного графа на тих самих вершинах і ребрах, до якої можна застосувати попередні аргументи для зовніпланарних графів[6]. Наприклад, на малюнку вгорі показано панциклічність графа октаедра, гамільтонового максимального планарного графа з шістьма вершинами. Строгіше, з тих самих причин, якщо максимальний планарний граф має цикл довжини , то він має цикли всіх менших довжин[7].
Графи Халіна є планарними графами, утвореними з планарного малюнка дерева, яке має вершин степеня два, доданням циклу, що з'єднує листки дерева. Графи Халіна не обов'язково панциклічні, але вони майже панциклічні в тому сенсі, що відсутній цикл максимум однієї довжини. Довжина відсутнього циклу обов'язково парна. Якщо жодна зі внутрішніх вершин графа Халіна не має степеня три, то граф обов'язково панциклічний[8].
1971 року помічено[1], що багато класичних умов для існування гамільтонового циклу достатні також для панциклічності, тому припущено, що будь-який 4-зв'язний планарний граф панциклічний, але незабаром знайдено сімейство контрприкладів[9].
Турнір — це напрямлений граф з однією напрямленою дугою між будь-якою парою вершин. Інтуїтивно турнір можна використати для моделювання кругової системи малюванням дуги від переможця до переможеного для кожної гри в змаганні. Турнір називають сильно зв'язним або просто сильним тоді й лише тоді, коли його не можна розділити на дві непорожні підмножини і тих, хто програв і виграв, так, що будь-який учасник перемагає будь-якого учасника в [10]. Будь-який сильний турнір є панциклічним[11] і вершинно панциклічним[12]. Якщо турнір регулярний (будь-який учасник має таке ж число виграшів і програшів, що й інші учасники), то він є також реберно панциклічним[13], однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.
Теорема Мантеля стверджує, що будь-який неорієнтований граф із вершинами, що має принаймні ребер і не має кратних ребер і петель, або містить трикутник, або він є повним двочастинним графом . Цю теорему можна посилити — будь-який неорієнтований гамільтонів граф з не менш ніж ребрами або панциклічний, або це [1].
Існують гамільтонові орієнтовані графи з вершинами і з дугами, які не є панциклічними, але будь-який гамільтонів орієнтований граф принаймні з дугами панциклічний. Крім того, строго зв'язний граф з вершинами, в якому кожна вершина має степінь, не менший від (вхідні та вихідні дуги рахуються разом), або панциклічний, або є повним двочастинним графом[14].
Для будь-якого графа його -й степінь графа визначається як граф на тій самій множині вершин, що має ребро між будь-якими двома вершинами, відстань між якими в не перевищує . Якщо вершинно 2-зв'язний, то за теоремою Фляйшнера є гамільтоновим графом. Твердження можна посилити: граф обов'язково буде вершинно панциклічним[15]. Строгіше, якщо є гамільтоновим, він також і панциклічний[16].
Перевірка графа на панциклічність є NP-повною задачею навіть для окремого випадку 3-зв'язних кубічних графів. NP-повною задачею є також перевірка графа на вершинну панциклічність навіть для окрмого випадку поліедральних графів[17]. Також NP-повною задачею є перевірка квадрата графа на гамільтоновість, а тим самим і перевірка на панциклічність[18].
Панциклічність уперше досліджували Харарі і Мозер у контексті турнірів[19], а також Муун[20] і Алпач[13]. Назву поняттю панциклічності дав Бонді, який розширив поняття для неорієнтованих графів[1].
- ↑ а б в г д Bondy, 1971.
- ↑ а б Randerath, Schiermeyer, Tewes, Volkmann, 2002.
- ↑ Schmeichel, Mitchem, 1982.
- ↑ Li, Corneil, Mendelsohn, 2000, Proposition 2.5.
- ↑ Helden, 2007, Corollary 3.78.
- ↑ Bernhart, Kainen, 1979.
- ↑ Hakimi, Schmeichel, 1979.
- ↑ Skowrońska, 1985.
- ↑ Malkevitch, 1971.
- ↑ Harary, Moser, 1966, Corollary 5b.
- ↑ Harary, Moser, 1966, Theorem 7.
- ↑ Moon, 1966, Theorem 1.
- ↑ а б Alspach, 1967.
- ↑ Häggkvist, Thomassen, 1976, с. 20–40.
- ↑ Hobbs, (1976).
- ↑ Fleischner, 1976.
- ↑ Li, Corneil, Mendelsohn, 2000, Theorems 2.3 и 2.4.
- ↑ Underground, (1978).
- ↑ Harary, Moser, 1966.
- ↑ Moon, 1966.
- Brian Alspach. Cycles of each length in regular tournaments // Canadian Mathematical Bulletin. — 1967. — Т. 10, вип. 2 (16 червня). — С. 283—286..
- Frank Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory, Series B. — 1979. — Т. 27, вип. 3 (16 червня). — С. 320—331. — DOI:..
- J. A. Bondy. Pancyclic graphs I // Journal of Combinatorial Theory, Series B. — 1971. — Т. 11, вип. 1 (16 червня). — С. 80—84. — DOI:..
- H. Fleischner. In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts // Monatshefte für Mathematik. — 1976. — Т. 82, вип. 2 (16 червня). — С. 125—149. — DOI:..
- Roland Häggkvist, Carsten Thomassen. On pancyclic digraphs // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20, вип. 1 (16 червня). — DOI:..
- S. L. Hakimi, E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph // Journal of Graph Theory. — 1979. — Т. 3 (16 червня). — С. 69—86. — DOI:..
- Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. — 1966. — Т. 73, вип. 3 (16 червня). — С. 231—246. — DOI:..
- Guido Helden. Hamiltonicity of maximal planar graphs and planar triangulations. — Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007. — (Dissertation).
- Arthur M. Hobbs. The square of a block is vertex pancyclic // Journal of Combinatorial Theory. — 1976. — Т. 20, вип. 1 (16 червня). — С. 1—4. — (Series B). — DOI:..
- Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вип. 3 (16 червня). — С. 219—225. — DOI:..
- Joseph Malkevitch. Recent Trends in Graph Theory. — Springer-Verlag, 1971. — Т. 186. — С. 191—195. — (Lecture Notes in Mathematics) — DOI:.
- J. W. Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. — 1966. — Т. 9, вип. 3 (16 червня). — С. 297—301. — DOI:..
- Bert Randerath, Ingo Schiermeyer, Meike Tewes, Lutz Volkmann. Vertex pancyclic graphs // Discrete Applied Mathematics. — 2002. — Т. 120, вип. 1—3 (16 червня). — С. 219—237. — DOI:..
- Edward Schmeichel, John Mitchem. Bipartite graphs with cycles of all even lengths // Journal of Graph Theory. — 1982. — Т. 6, вип. 4 (16 червня). — С. 429—439. — DOI:..
- Mirosława Skowrońska. Cycles in Graphs / Brian R. Alspach, Christopher D. Godsil. — Elsevier Science Publishers B.V, 1985. — Т. 27. — С. 179—194. — (Annals of Discrete Mathematics).
- Paris Underground. On graphs with Hamiltonian squares // Discrete Mathematics. — 1978. — Т. 21, вип. 3 (16 червня). — С. 323. — DOI:..
- Weisstein, Eric W. Панциклічний граф(англ.) на сайті Wolfram MathWorld.
