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

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

Граф Дюрера G(6,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² ≡ ±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² ≡ 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].

Див. також

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