Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.
Определение и обозначение В обозначениях Воткинса 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-угольника и звезды, из которых граф образован. Любой обобщённый граф Петерсена можно построить как из графа с двумя вершинами, двумя петлями и ещё одним ребром.
Граф Петерсена сам по себе 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(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). Только эти семь графов являются симметричными обобщёнными графами Петерсена. Он является двудольным в том и только в том случае, когда 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. Во всех других случаях он имеет гамильтонов цикл. Если n сравним с 3 по модулю 6 и k равен 2, G(n,k) имеет ровно три гамильтоновых цикла, для G(n,2) число гамильтоновых циклов можно вычислить по формуле, зависящей от классов n по модулю шесть, и вовлекает числа Фибоначчи.
Граф Петерсена является единственным обобщённым графом Петерсена, который нельзя раскрасить рёберно в 3 цвета. Обобщённый граф Петерсена G(9,2) является одним из немногих известных графов, который нельзя раскрасить рёберно в 3 цвета Reprint издания 1978 Academic Press.
Любой обобщённый граф Петерсена является графом единичных расстояний.
Примечания
Категория:Теория графов Категория:Регулярные графы Категория:Параметрические семейства графов