Generalized Petersen graph

Last updated February 11, 2024

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter ^[1] and was given its name in 1969 by Mark Watkins.^[2]

Definition and notation

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

\{u_{0},u_{1},\ldots ,u_{n-1},v_{0},v_{1},\ldots ,v_{n-1}\}

and edge set

\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\mid 0\leq i\leq n-1\}

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.^[3]

Examples

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).^[4]

Properties

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).^[5] 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.^[6] When n is congruent to 3 modulo 6 G(n, 2) has exactly three Hamiltonian cycles.^[7] 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.^[8]
Every generalized Petersen graph is a unit distance graph.^[9]

Isomorphisms

G(n, k) is isomorphic to G(n, l) if and only if k=l or kl ≡ ±1 (mod n).^[10]

Girth

The girth of G(n, k) is at least 3 and at most 8, in particular:^[11]

g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.

A table with exact girth values:

Condition	Girth
$n=3k$	3
$n=4k$	4
$k=1$	4
$n=5k$	5
$n=5k/2$
$k=2$
$n=6k$	6
$k=3$
$n=2k+2$
$n=7k$	7
$n=7k/2$
$n=7k/3$
$k=4$
$n=2k+3$
$n=3k\pm 2$
otherwise	8

Chromatic number and chromatic index

Being regular, according to Brooks' theorem their chromatic number can not be larger than their degree. Generalized Petersen graphs are cubic, so their chromatic number can be either 2 or 3. More exactly:

\chi (G(n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\\\end{cases}}

Where $\land$ denotes the logical AND, while $\lor$ the logical OR. For example, the chromatic number of $G(5,2)$ is 3.

A 3-coloring of the Petersen graph or $G(5,2)$
A 2-coloring of the Desargues graph or $G(10,3)$
A 3-coloring of the Dürer graph or $G(6,2)$

Petersen graph, being a snark, has a chromatic index of 4. All other generalized Petersen graph has chromatic index 3.^[12]

The generalized Petersen graph G(9, 2) is one of the few graphs known to have only one 3-edge-coloring.^[13]

A 4-edge-coloring of the Petersen graph or $G(5,2)$
A 3-edge-coloring of the Dürer graph or $G(6,2)$
A 3-edge-coloring of the dodecahedron or $G(10,2)$
A 3-edge-coloring of the Desargues graph or $G(10,3)$
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.^[14]

Perfect Colorings

All admissible matrices of all perfect 2-colorings of the graphs G(n, 2) and G(n, 3) are enumerated.^[15]

Admissible matrices
	G(n, 2)	G(n, 3)
${\begin{bmatrix}2&1\\1&2\end{bmatrix}}$	All graphs	All graphs
${\begin{bmatrix}2&1\\2&1\end{bmatrix}}$	Just G(3m, 2)	No graphs
${\begin{bmatrix}1&2\\2&1\end{bmatrix}}$	No graphs	Just G(2m,3)
${\begin{bmatrix}0&3\\1&2\end{bmatrix}}$	No graphs	Just G(4m,3)
${\begin{bmatrix}0&3\\2&1\end{bmatrix}}$	Just G(5m,2)	Just G(5m,3)
${\begin{bmatrix}0&3\\3&0\end{bmatrix}}$	No graphs	Just G(2m,3)

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, the Kneser graph $K (n, k)$ (alternatively $KG n, k$ ) is the graph whose vertices correspond to the $k$ -element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski. The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.

In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered simple convex polyhedra.

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

References

↑ Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society , 56 (5): 413–455, doi: 10.1090/S0002-9904-1950-09407-5 .
↑ Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory , 6 (2): 152–164, doi: 10.1016/S0021-9800(69)80116-X .
↑ Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological Graph Theory, New York: Wiley. Example 2.1.2, p.58.
↑ Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, MR 1220613 .
↑ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society, 70 (2): 211–218, doi:10.1017/S0305004100049811 .
↑ Alspach, B. R. (1983), "The classification of Hamiltonian generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 34 (3): 293–312, doi: 10.1016/0095-8956(83)90042-4 , MR 0714452 .
↑ Thomason, Andrew (1982), "Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable", Journal of Graph Theory , 6 (2): 219–221, doi:10.1002/jgt.3190060218 .
↑ Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 47 (1): 53–59, doi: 10.1016/0095-8956(89)90064-6 , MR 1007713 .
↑ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, vol. 1109.
↑ Steimle, Alice; Staton, William (2009), "The isomorphism classes of the generalized Petersen graphs", Discrete Mathematics , 309 (1): 231–237, doi: 10.1016/j.disc.2007.12.074
↑ Ferrero, Daniela; Hanusch, Sarah (2014), "Component connectivity of generalized Petersen graphs" (PDF), International Journal of Computer Mathematics, 91 (9): 1940–1963, doi:10.1080/00207160.2013.878023, ISSN 0020-7160, archived from the original (PDF) on 2018-10-20, retrieved 2018-10-20
↑ Castagna, Frank; Prins, Geert Caleb Ernst (1972), "Every generalized Petersen graph has a Tait coloring", Pacific Journal of Mathematics, 40 (1): 53–58, doi: 10.2140/pjm.1972.40.53 , ISSN 0030-8730, MR 0304223, Zbl 0236.05106
↑ Bollobás, Béla (2004), Extremal Graph Theory, Dover, p. 233. Reprint of 1978 Academic Press edition.
↑ Castagna, Frank; Prins, Geert (1972), "Every Generalized Petersen Graph has a Tait Coloring", Pacific Journal of Mathematics , 40: 53–58, doi: 10.2140/pjm.1972.40.53 .
↑ Karami, Hamed (2022), "Perfect 2-colorings of the generalized Petersen graph GP(n,3)", Electronic Journal of Graph Theory and Applications, 10: 239–245, arXiv: 2009.07120 , doi: 10.5614/ejgta.2022.10.1.16 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society , 56 (5): 413–455, doi: 10.1090/S0002-9904-1950-09407-5 .

[2] Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory , 6 (2): 152–164, doi: 10.1016/S0021-9800(69)80116-X .

[3] Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological Graph Theory, New York: Wiley. Example 2.1.2, p.58.

[4] Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, MR 1220613 .

[5] Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society, 70 (2): 211–218, doi:10.1017/S0305004100049811 .

[6] Alspach, B. R. (1983), "The classification of Hamiltonian generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 34 (3): 293–312, doi: 10.1016/0095-8956(83)90042-4 , MR 0714452 .

[7] Thomason, Andrew (1982), "Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable", Journal of Graph Theory , 6 (2): 219–221, doi:10.1002/jgt.3190060218 .

[8] Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 47 (1): 53–59, doi: 10.1016/0095-8956(89)90064-6 , MR 1007713 .

[9] Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, vol. 1109.

[10] Steimle, Alice; Staton, William (2009), "The isomorphism classes of the generalized Petersen graphs", Discrete Mathematics , 309 (1): 231–237, doi: 10.1016/j.disc.2007.12.074

[FH-11] Ferrero, Daniela; Hanusch, Sarah (2014), "Component connectivity of generalized Petersen graphs" (PDF), International Journal of Computer Mathematics, 91 (9): 1940–1963, doi:10.1080/00207160.2013.878023, ISSN 0020-7160, archived from the original (PDF) on 2018-10-20, retrieved 2018-10-20

[12] Castagna, Frank; Prins, Geert Caleb Ernst (1972), "Every generalized Petersen graph has a Tait coloring", Pacific Journal of Mathematics, 40 (1): 53–58, doi: 10.2140/pjm.1972.40.53 , ISSN 0030-8730, MR 0304223, Zbl 0236.05106

[13] Bollobás, Béla (2004), Extremal Graph Theory, Dover, p. 233. Reprint of 1978 Academic Press edition.

[14] Castagna, Frank; Prins, Geert (1972), "Every Generalized Petersen Graph has a Tait Coloring", Pacific Journal of Mathematics , 40: 53–58, doi: 10.2140/pjm.1972.40.53 .

[15] Karami, Hamed (2022), "Perfect 2-colorings of the generalized Petersen graph GP(n,3)", Electronic Journal of Graph Theory and Applications, 10: 239–245, arXiv: 2009.07120 , doi: 10.5614/ejgta.2022.10.1.16 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]