Русская Википедия:Обобщённый граф Петерсена
Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 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-угольника и звезды, из которых граф образован. Любой обобщённый граф Петерсена можно построить как Шаблон:Не переведено 5 из графа с двумя вершинами, двумя петлями и ещё одним ребром[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].
Примечания
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга Reprint издания 1978 Academic Press
- ↑ Шаблон:Статья
