Обобщённый граф Петерсена

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

Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.

Определение и обозначение

В обозначениях Воткинса 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-угольника и звезды, из которых граф образован. Любой обобщённый граф Петерсена можно построить как граф напряжений из графа с двумя вершинами, двумя петлями и ещё одним ребром.

Граф Петерсена сам по себе 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-связными и хорошо покрытыми (что означает, что все его наибольшие независимые множества имеют один и тот же размер).

Свойства

Один из трёх гамильтоновых циклов в 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). Только эти семь графов являются симметричными обобщёнными графами Петерсена.
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. Во всех других случаях он имеет гамильтонов цикл. Если n сравним с 3 по модулю 6 и k равен 2, G(n,k) имеет ровно три гамильтоновых цикла, для G(n,2) число гамильтоновых циклов можно вычислить по формуле, зависящей от классов n по модулю шесть, и вовлекает числа Фибоначчи.

Граф Петерсена является единственным обобщённым графом Петерсена, который нельзя раскрасить рёберно в 3 цвета. Обобщённый граф Петерсена G(9,2) является одним из немногих известных графов, который нельзя раскрасить рёберно в 3 цвета.

Любой обобщённый граф Петерсена является графом единичных расстояний.