В обозначениях Воткинса G(n,k) — это граф с множеством вершин
{u0, u1, ..., un−1, v0, v1, ..., vn−1}
и множеством рёбер
{uiui+1, uivi, vivi+k: i = 0,...,n − 1}
где индексы берутся по модулю n и k < n/2. Обозначением Коксетера для того же графа будет {n}+{n/k},
комбинация из символа Шлефли для правильного n-угольника и звезды, из которых граф образован. Любой обобщённый граф Петерсена можно построить как граф напряжений[англ.] из графа с двумя вершинами, двумя петлями и ещё одним ребром[3].
Один из трёх гамильтоновых циклов в G(9,2). Два других гамильтоновых цикла в том же самом графе получаются вращением на 40°.
Это семейство графов обладает рядом интересных свойств. Например:
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].
↑Jonathan L. Gross, Thomas W. Tucker.Пример 2.1.2. // Topological Graph Theory. — New York: Wiley, 1987. — С. 58.
↑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. — С. 193—212.
↑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.
