Узагальнений граф Петерсена
Матеріал з Вікіпедії — вільної енциклопедії.
В теорії графів узагальненими графами Петерсена називають сімейство кубічних графів, утворене з'єднанням вершин правильного багатокутника з відповідними вершинами зірки. Сімейство містить граф Петерсена і узагальнює один зі шляхів побудови графу Петерсена. Сімейство узагальнених графів Петерсена ввів у розгляд в 1950 році Коксетер[1] і назву цим графам дав у 1969 році Марк Воткінс[2].
У позначеннях Воткінса G(n,k) — це граф з множиною вершин
- {u0, u1, …, un-1, v0, v1, …, vn-1}
і множиною ребер
- {ui ui+1, ui vi, vi vi+k: i = 0,…,n − 1}
де індекси беруться за модулем n і k < n/2. Позначенням Коксетера для того ж графу буде {n}+{n/k}, комбінація зі символу Шлефлі для правильного n-кутника та зірки, з яких граф утворено. Будь-який узагальнений граф Петерсена можна побудувати як граф напруг[en] з графу з двома вершинами, двома петлями і ще одним ребром[3].
Граф Петерсена сам по собі G(5,2) або {5}+{5/2}.
До узагальнених графів Петерсена належать n-призма G(n,1), граф Дюрера G(6,2), граф Мебіуса — Кантора G(8,3), додекаедр G(10,2), граф Дезарга G(10,3) і граф Науру G(12,5).
Чотири узагальнених графи Петерсена — трикутна призма, 5-кутна призма, граф Дюрера і G(7,2) належать до семи графів, що є кубічними, вершинно-3-зв'язковими і добре покритими (що означає, що всі його найбільші незалежні множини мають однаковий розмір)[4].
Це сімейство графів має низку цікавих властивостей. Наприклад:
- G(n,k) є вершинно-транзитивним (означає, що є симетрії, які переводять будь-яку вершину в будь-яку іншу) тоді і тільки тоді, коли n = 10 і k =2, або якщо k2 ≡ ±1 (mod n).
- Він є реберно-транзитивним (має симетрії, які переводять будь-яке ребро в будь-яке інше) лише в таких семи випадках: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5)[5]. Тільки ці сім графів є симетричними узагальненими графами Петерсена.
- Він є двочастковим у тому і тільки в тому випадку, коли n парне і k непарне.
- Він є графом Келі в тому і тільки в тому випадку, коли k2 ≡ 1 (mod n).
- Він є гіпогамільтоновим, якщо n порівнянне з 5 за модулем 6 і k дорівнює 2, n-2, (n+1)/2, або (n-1)/2 (всі чотири з цих значень k призводять до ізоморфним графів). Він не є гамільтоновим, якщо n ділиться на чотири, щонайменше при значенні 8, і k рівному n/2. У всіх інших випадках він має гамільтонів цикл[6]. Якщо n порівнянне з 3 за модулем 6 і k дорівнює 2, G(n,k) має рівно три гамільтонових цикли[7], для G(n,2) число гамільтонових циклів можна обчислити за формулою, що залежить від класів n за модулем шість і залучає числа Фібоначчі[8].
Граф Петерсена є єдиним узагальненим графом Петерсена, який не можна розфарбувати реберно в 3 кольори[9]. Узагальнений граф Петерсена G(9,2) є одним з небагатьох відомих графів, який не можна розфарбувати реберно в 3 кольори[10].
Будь-який узагальнений граф Петерсена є графом одиничних відстаней[11].
- ↑ H. S. M. Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society. — 1950. — Т. 56 (4 вересня). — С. 413—455. — DOI:.
- ↑ Mark E. Watkins. A Theorem on Tait Colorings with an Application to the generalized Petersen graphs // Journal of Combinatorial Theory. — 1969. — Т. 6 (4 вересня). — С. 152—164. — DOI:.
- ↑ Jonathan L. Gross, Thomas W. Tucker. Пример 2.1.2. // Topological Graph Theory. — New York : Wiley, 1987. — С. 58.
- ↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. A characterisation of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1993. — Т. 13 (4 вересня). — С. 193—212.
- ↑ R. Frucht, J. E. Graver, M. E. Watkins. The groups of the generalized Petersen graphs // Proceedings of the Cambridge Philosophical Society. — 1971. — Т. 70. — С. 211—218. — DOI:.
- ↑ B. R. Alspach. The classification of Hamiltonian generalized Petersen graphs // Journal of Combinatorial Theory, Series B. — 1983. — Т. 34. — С. 293—312. — DOI:.
- ↑ Andrew Thomason. Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable // Journal of Graph Theory. — 1982. — Т. 6, вип. 2. — С. 219—221. — DOI:.
- ↑ Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вип. 1. — С. 53—59. — (Series B). — DOI:.
- ↑ Frank Castagna, Geert Prins. Every generalized Petersen graph has a Tait Coloring // Pacific Journal of Mathematics. — 1972. — Т. 40.
- ↑ Béla Bollobás. Extremal Graph Theory. — Dover, 2004. — С. 233. Reprint издания 1978 Academic Press
- ↑ Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs. — 2010. — Т. 1109.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
