Теорема Фляйшнера

Вершинно 2-зв'язний граф, його квадрат і гамільтонів цикл у квадраті

Теорема Фляйшнера — твердження в теорії графів, що дає достатню умову, щоб граф містив гамільтонів цикл: якщо граф $G$ є 2-вершинно-зв'язним, то квадрат графа $G$ гамільтонів. Названа ім'ям Герберта Фляйшнера, який опублікував доведення теореми 1974 року.

Визначення та твердження

Неорієнтований граф G є гамільтоновим, якщо він містить цикл, який проходить через кожну вершину рівно один раз. Граф є 2-вершинно-зв'язним, якщо він не містить зчленувальних вершин, тобто вершин, видалення яких робить граф, що залишився, незв'язним. Не будь-який 2-вершинно-зв'язний граф є гамільтоновим. Контрприкладами є граф Петерсена та повний двоковий граф K_2,3.

Квадрат графа G — це граф G², який має ту саму множину вершин, що й граф G, і в якому дві вершини суміжні тоді й лише тоді, коли відстань між ними в G не перевищує 2. Теорема Фляйшнера стверджує, що квадрат скінченного 2-вершинно-зв'язного графа з трьома і більше вершинами завжди гамільтонів. Еквівалентно, вершини будь-якого 2-вершинно-зв'язного графа G можна організувати в циклічний порядок, так що відстань у графі G між вершинами, суміжними в цьому порядку, не перевищує 2.

Розширення

У теоремі Фляйшнера можна накласти обмеження на гамільтонів цикл так, щоб він включав три вибраних ребра, які проходять через дві вибрані вершини.

Крім наявності гамільтонового циклу, квадрат 2-вершинно-зв'язного графа G має бути також гамільтоново пов'язаним (що означає, що він має гамільтонів шлях, який починається і закінчується в будь-яких двох вибраних вершинах) і 1-гамільтонів (що означає, що якщо видалити будь-яку вершину, граф, що залишився, також міститиме гамільтонів цикл). Граф має бути також вершинно панциклічним, що означає, що для будь-якої вершини v та будь-якого цілого k з 3 ≤ k ≤ |V(G)| існує цикл довжини k, що містить v .

Якщо граф G не 2-вершинно-зв'язний, його квадрат може мати, а може і не мати гамільтонового циклу і визначення, чи має граф такий цикл, є NP-повною задачею.

Нескінченний граф не може мати гамільтонового циклу, оскільки будь-який цикл скінченний, але Карстен Томассен довів, що у випадку, коли G є нескінченним локально скінченним 2-вершинно-зв'язним графом з єдиним кінцем, то G² обов'язково має двічі нескінченний гамільтонів шлях. Загальніше, якщо G локально скінченний, 2-вершинно-зв'язний і має будь-яке число кінців, то G² має гамільтонів цикл. У компактному топологічному просторі, утвореному розглядом графа як симпліційного комплексу і доданням точки на нескінченності для кожного кінця графа, гамільтонів цикл визначають як підпростір, який гомеоморфний евклідовому колу і покриває всі вершини.

Історія

Про доведення теореми Герберт Фляйшнер оголосив 1971 року й опублікував 1974 року, вирішивши цим гіпотезу 1966 року Неш-Вільямса, яку незалежно висловили також Л. В. Байник і Пламмер. У своєму огляді статті Фляйшнера Неш-Вільямс пише, що той вирішив «добре відому проблему, об яку кілька років розбивалася винахідливість інших теоретиків теорії графів».

Оригінальне доведення Фляйшнера було складним. Вацлав Хватал у праці, в якій він увів поняття жорсткості графа, зауважив, що квадрат k-вершинно-зв'язного графа обов'язково k-жорсткий. Він висловив припущення, що 2-жорсткі графи є гамільтоновими, з чого вийшло б інше доведення теореми Фляйшнера. Пізніше виявлено контрприклади до цієї гіпотези, але можливість, що зі скінченної межі жорсткості могла б випливати гамільтоновість, залишилася важливою відкритою проблемою теорії графів. Простіше доведення як теореми Фляйшнера, так і її розширень, які зробили Чартранд, Хоббс, Янг і Капуур, надав Ріха, а ще одне спрощене доведення теореми надав Георгакопулус.

Література

• D. Bauer, H. J. Broersma, H. J. Veldman. Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997) // Discrete Applied Mathematics. — 2000. — Vol. 99, no. 1—3. — P. 317–321. — DOI:10.1016/S0166-218X(99)00141-9.
• J. A. Bondy. Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971). — Baton Rouge, Louisiana : Louisiana State University, 1971. — P. 167–172.
• G. Chartrand, Arthur M. Hobbs, H. A. Jung, S. F. Kapoor, C. St. J. A. Nash-Williams. The square of a block is Hamiltonian connected // Journal of Combinatorial Theory. — 1974. — Vol. 16. — P. 290–292. — (Series B). — DOI:10.1016/0095-8956(74)90075-6.
• Václav Chvátal. Tough graphs and Hamiltonian circuits // Discrete Mathematics. — 1973. — Vol. 5, iss. 3. — P. 215–228. — DOI:10.1016/0012-365X(73)90138-6.
• Herbert Fleischner. The square of every two-connected graph is Hamiltonian // Journal of Combinatorial Theory. — 1974. — Vol. 16. — (Series B). — DOI:10.1016/0095-8956(74)90091-4.
• H. Fleischner. In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts // Monatshefte für Mathematik. — 1976. — Vol. 82, iss. 2. — DOI:10.1007/BF01305995.
• Agelos Georgakopoulos. A short proof of Fleischner's theorem // Discrete Mathematics. — 2009a. — Vol. 309, iss. 23—24. — P. 6632–6634. — DOI:10.1016/j.disc.2009.06.024.
• Agelos Georgakopoulos. Infinite Hamilton cycles in squares of locally finite graphs // Advances in Mathematics. — 2009b. — Vol. 220, iss. 3. — P. 670–705. — DOI:10.1016/j.aim.2008.09.014.
• Arthur M. Hobbs. The square of a block is vertex pancyclic // Journal of Combinatorial Theory. — 1976. — Vol. 20, iss. 1. — P. 1–4. — (Series B). — DOI:10.1016/0095-8956(76)90061-7.
• Janina Müttel, Dieter Rautenbach. A short proof of the versatile version of Fleischner’s theorem // Discrete Mathematics. — 2012. — DOI:10.1016/j.disc.2012.07.032.
• Stanislav Říha. A new proof of the theorem by Fleischner // Journal of Combinatorial Theory. — 1991. — Vol. 52, iss. 1. — P. 117–123. — (Series B). — DOI:10.1016/0095-8956(91)90098-5.
• Carsten Thomassen. Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) / B. Bollobás. — Elsevier, 1978. — Т. 3. — С. 269–277. — (Annals of Discrete Mathematics) — ISBN 978-0-7204-0843-0. — DOI:10.1016/S0167-5060(08)70512-0.
• Paris Underground. On graphs with Hamiltonian squares // Discrete Mathematics. — 1978. — Vol. 21, iss. 3. — P. 323. — DOI:10.1016/0012-365X(78)90164-4.
• J. A. Bondy. Handbook of combinatorics, Vol. 1, 2. — Amsterdam : Elsevier, 1995. — С. 3–110.
• Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 139. — ISBN 9781439826270.
• Reinhard Diestel. Graph Theory. — corrected 4th electronic. — 2012.