Generalized Petersen graph

In Watkins' notation, G(n, k) is a graph with vertex set

:$\backslash \{u\_0,\; u\_1,\; \backslash ldots,\; u\_\{n-1\},\; v\_0,\; v\_1,\; \backslash ldots,\; v\_\{n-1\}\backslash \}$

and edge set

:$\backslash \{u\_iu\_\{i+1\},\; u\_iv\_i,\; v\_iv\_\{i+k\}\; \backslash mid\; 0\; \backslash le\; i\; \backslash le\; n-1\; \backslash \}$

where subscripts are to be read modulo n and k < n/2. Some authors use the notation GPG(n, k). Coxeter's notation for the same graph would be {n} + {n/k}, a combination of the Schläfli symbols for the regular n-gon and star polygon from which the graph is formed. The Petersen graph itself is G(5, 2) or {5} + {5/2}.

Any generalized Petersen graph can also be constructed from a voltage graph with two vertices, two self-loops, and one other edge.{{citation | last1 = Gross | first1 = Jonathan L. | last2 = Tucker | first2 = Thomas W. | location = New York | publisher = Wiley | title = Topological Graph Theory | year = 1987}}. Example 2.1.2, p.58.

Among the generalized Petersen graphs are the n-prism G(n, 1), the Dürer graph G(6, 2), the Möbius-Kantor graph G(8, 3), the dodecahedron G(10, 2), the Desargues graph G(10, 3) and the Nauru graph G(12, 5).

Four generalized Petersen graphs – the 3-prism, the 5-prism, the Dürer graph, and G(7, 2) – are among the seven graphs that are cubic, 3-vertex-connected, and well-covered (meaning that all of their maximal independent sets have equal size).{{citation | last1 = Campbell | first1 = S. R. | last2 = Ellingham | first2 = M. N. | author2-link = Mark Ellingham | last3 = Royle | first3 = Gordon F. | author3-link = Gordon Royle | journal = Journal of Combinatorial Mathematics and Combinatorial Computing | mr = 1220613 | pages = 193–212 | title = A characterisation of well-covered cubic graphs | volume = 13 | year = 1993}}.

File:Generalized Petersen 9 2 Hamiltonicity.svg

This family of graphs possesses a number of interesting properties. For example:

• G(n, k) is vertex-transitive (meaning that it has symmetries that take any vertex to any other vertex) if and only if (n, k) = (10, 2) or k² ≡ ±1 (mod n).
• G(n, k) is edge-transitive (having symmetries that take any edge to any other edge) only in the following seven cases: (n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5).{{citation | last1 = Frucht | first1 = R. | author1-link = R. Frucht | last2 = Graver | first2 = J. E. | last3 = Watkins | first3 = M. E. | doi = 10.1017/S0305004100049811 | journal = Proceedings of the Cambridge Philosophical Society | pages = 211–218 | title = The groups of the generalized Petersen graphs | volume = 70 | issue = 2 | year = 1971}}. These seven graphs are therefore the only symmetric generalized Petersen graphs.
• G(n, k) is bipartite if and only if n is even and k is odd.
• G(n, k) is a Cayley graph if and only if k² ≡ 1 (mod n).
• G(n, k) is hypohamiltonian when n is congruent to 5 modulo 6 and k = 2, n − 2, or (n ± 1)/2 (these four choices of k lead to isomorphic graphs). It is also non-Hamiltonian when n is divisible by 4, at least equal to 8, and k = n/2. In all other cases it has a Hamiltonian cycle.{{citation | last = Alspach | first = B. R. | authorlink = Brian Alspach | doi = 10.1016/0095-8956(83)90042-4 | mr = 0714452 | journal = Journal of Combinatorial Theory | series=Series B | pages = 293–312 | title = The classification of Hamiltonian generalized Petersen graphs | volume = 34 | issue = 3 | year = 1983| doi-access = free }}. When n is congruent to 3 modulo 6 G(n, 2) has exactly three Hamiltonian cycles.{{citation|title=Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable|first=Andrew|last=Thomason|doi=10.1002/jgt.3190060218|journal=Journal of Graph Theory| volume=6 |issue=2 |year=1982|pages=219–221}}. For G(n, 2), the number of Hamiltonian cycles can be computed by a formula that depends on the congruence class of n modulo 6 and involves the Fibonacci numbers.{{citation | last = Schwenk | first = Allen J. | doi = 10.1016/0095-8956(89)90064-6 | issue = 1 | journal = Journal of Combinatorial Theory | series = Series B | mr = 1007713 | pages = 53–59 | title = Enumeration of Hamiltonian cycles in certain generalized Petersen graphs | volume = 47 | year = 1989| doi-access = free }}.
• Every generalized Petersen graph is a unit distance graph.{{citation | last1 = Žitnik | first1 = Arjana | last2 = Horvat | first2 = Boris | last3 = Pisanski | first3 = Tomaž | author3-link = Tomaž Pisanski | series = IMFM preprints | title = All generalized Petersen graphs are unit-distance graphs | url = http://preprinti.imfm.si/PDF/01109.pdf | volume = 1109 | year = 2010 | access-date = 2017-04-07 | archive-date = 2018-07-24 | archive-url = https://web.archive.org/web/20180724094410/http://preprinti.imfm.si/PDF/01109.pdf | url-status = dead }}.

G(n, k) is isomorphic to G(n, l) if and only if k ≡ ±l (mod n) or kl ≡ ±1 (mod n).{{citation|title=The isomorphism classes of the generalized Petersen graphs|first=Alice|last=Steimle| first2=William|last2=Staton|journal=Discrete Mathematics| volume=309| issue=1 |year=2009 |pages=231–237 |doi=10.1016/j.disc.2007.12.074 |doi-access=free}}

The girth of G(n, k) is at least 3 and at most 8, in particular:{{Citation | url= http://danielaferrero.wp.txstate.edu/files/2015/03/Component-connectivity-generalized-Petersen-graphs.pdf | doi= 10.1080/00207160.2013.878023 | journal= International Journal of Computer Mathematics | first1=Daniela | last1=Ferrero |author1-link=Daniela Ferrero| first2=Sarah | last2=Hanusch | pages=1940–1963 | volume=91 | issue=9 | year=2014 | title=Component connectivity of generalized Petersen graphs | issn=0020-7160 | access-date=2018-10-20 | archive-url= https://web.archive.org/web/20181020182041/http://danielaferrero.wp.txstate.edu/files/2015/03/Component-connectivity-generalized-Petersen-graphs.pdf | archive-date=2018-10-20 | url-status=dead }}

:$g(G(n,k))\; \backslash le\; \backslash min\; \backslash left\; \backslash \{8,k+3,\backslash frac\{n\}\{\backslash gcd(n,k)\}\; \backslash right\; \backslash \}.$

A table with exact girth values:

Generalized Petersen graphs are regular graphs of degree three, so according to Brooks' theorem their chromatic number can only be two or three. More exactly:

:$\backslash chi(G(n,k))=\; \backslash begin\{cases\}$

2 & 2 \mid n \land 2 \nmid k \\

3 & 2 \nmid n \lor 2 \mid k \\

\end{cases}

Where $\backslash land$ denotes the logical AND, while $\backslash lor$ the logical OR. Here, $\backslash mid$ denotes divisibility, and $\backslash nmid$ denotes its negation. For example, the chromatic number of $G(5,2)$ is 3.

Petersen_graph_3-coloring.svg|A 3-coloring of the Petersen graph or $G(5,2)$

Desargues graph 2COL.svg|A 2-coloring of the Desargues graph or $G(10,3)$

Dürer graph 3COL.svg|A 3-coloring of the Dürer graph or $G(6,2)$

The Petersen graph, being a snark, has a chromatic index of 4: its edges require four colors. All other generalized Petersen graphs have chromatic index 3. These are the only possibilities, by Vizing's theorem.{{citation | last1 = Castagna | first1 = Frank | last2 = Prins | first2 = Geert Caleb Ernst | journal = Pacific Journal of Mathematics | title = Every generalized Petersen graph has a Tait coloring | volume = 40 | issue = 1 | pages = 53–58 | year = 1972 | doi = 10.2140/pjm.1972.40.53|issn=0030-8730|mr=304223|zbl=0236.05106| doi-access = free}}

The generalized Petersen graph G(9, 2) is one of the few graphs known to have only one 3-edge-coloring.{{citation|first=Béla|last=Bollobás|authorlink=Béla Bollobás|title=Extremal Graph Theory|publisher=Dover|year=2004|page=233}}. Reprint of 1978 Academic Press edition.

PetersenBarveniHran.svg|A 4-edge-coloring of the Petersen graph or $G(5,2)$

Dürer graph 3color edge.svg|A 3-edge-coloring of the Dürer graph or $G(6,2)$

3-colored dodecahedron.svg|A 3-edge-coloring of the dodecahedron or $G(10,2)$

Desargues graph 3color edge.svg|A 3-edge-coloring of the Desargues graph or $G(10,3)$

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); matrices.svg|A 3-edge-coloring of the Nauru graph or $G(12,5)$

The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable.{{citation | last1 = Castagna | first1 = Frank | last2 = Prins | first2 = Geert | journal = Pacific Journal of Mathematics | title = Every Generalized Petersen Graph has a Tait Coloring | volume = 40 | pages = 53–58 | year = 1972 | doi = 10.2140/pjm.1972.40.53 | doi-access = free }}.

All admissible matrices of all perfect 2-colorings of the graphs G(n, 2) and G(n, 3) are enumerated.{{citation | last = Karami| first = Hamed | journal = Electronic Journal of Graph Theory and Applications | title = Perfect 2-colorings of the generalized Petersen graph GP(n,3) | volume = 10 | pages = 239–245 | year = 2022 | doi =

10.5614/ejgta.2022.10.1.16 | doi-access = free | arxiv = 2009.07120 }}.

{{reflist}}

Category:Parametric families of graphs

Category:Regular graphs