Узагальнений граф Петерсена

Граф Дюрера G(6,2).

В теорії графів узагальненими графами Петерсена називають сімейство кубічних графів, утворене з'єднанням вершин правильного багатокутника з відповідними вершинами зірки. Сімейство містить граф Петерсена і узагальнює один зі шляхів побудови графу Петерсена. Сімейство узагальнених графів Петерсена ввів у розгляд в 1950 році Коксетер[1] і назву цим графам дав у 1969 році Марк Воткінс[2].

Визначення і позначення

У позначеннях Воткінса G(n,k) — це граф з множиною вершин

{u₀, u₁, …, u_n-1, v₀, v₁, …, v_n-1}

і множиною ребер

{u_i u_i+1, u_i v_i, v_i v_i+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(9,2). Два інших гамільтонових цикли в тому самому графі отримують обертанням на 40°.

Це сімейство графів має низку цікавих властивостей. Наприклад:

1. G(n,k) є вершинно-транзитивним (означає, що є симетрії, які переводять будь-яку вершину в будь-яку іншу) тоді і тільки тоді, коли n = 10 і k =2, або якщо k^2 ≡ ±1 (mod n).
2. Він є реберно-транзитивним (має симетрії, які переводять будь-яке ребро в будь-яке інше) лише в таких семи випадках: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5)[5]. Тільки ці сім графів є симетричними узагальненими графами Петерсена.
3. Він є двочастковим у тому і тільки в тому випадку, коли n парне і k непарне.
4. Він є графом Келі в тому і тільки в тому випадку, коли k^2 ≡ 1 (mod n).
5. Він є гіпогамільтоновим, якщо 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].

Див. також

• Граф Петерсена
• Кубічний граф

Примітки

1. H. S. M. Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society. — 1950. — Т. 56 (16 січня). — С. 413—455. — DOI:10.1090/S0002-9904-1950-09407-5.
2. Mark E. Watkins. A Theorem on Tait Colorings with an Application to the generalized Petersen graphs // Journal of Combinatorial Theory. — 1969. — Т. 6 (16 січня). — С. 152—164. — DOI:10.1016/S0021-9800(69)80116-X.
3. Jonathan L. Gross, Thomas W. Tucker. Пример 2.1.2. // Topological Graph Theory. — New York : Wiley, 1987. — С. 58.
4. 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 (16 січня). — С. 193—212.
5. 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:10.1017/S0305004100049811.
6. B. R. Alspach. The classification of Hamiltonian generalized Petersen graphs // Journal of Combinatorial Theory, Series B. — 1983. — Т. 34. — С. 293—312. — DOI:10.1016/0095-8956(83)90042-4.
7. Andrew Thomason. Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable // Journal of Graph Theory. — 1982. — Т. 6, вип. 2. — С. 219—221. — DOI:10.1002/jgt.3190060218.
8. Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вип. 1. — С. 53—59. — (Series B). — DOI:10.1016/0095-8956(89)90064-6.
9. Frank Castagna, Geert Prins. Every generalized Petersen graph has a Tait Coloring // Pacific Journal of Mathematics. — 1972. — Т. 40.
10. Béla Bollobás. Extremal Graph Theory. — Dover, 2004. — С. 233. Reprint издания 1978 Academic Press
11. Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs. — 2010. — Т. 1109.