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]

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

A table with exact girth values:

Condition	Girth
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle 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:

${\displaystyle \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 ${\displaystyle \land }$ denotes the logical AND, while ${\displaystyle \lor }$ the logical OR. For example, the chromatic number of ${\displaystyle G(5,2)}$ is 3.

• 
  A 3-coloring of the Petersen graph or ${\displaystyle G(5,2)}$
• 
  A 2-coloring of the Desargues graph or ${\displaystyle G(10,3)}$
• 
  A 3-coloring of the Dürer graph or ${\displaystyle 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 ${\displaystyle G(5,2)}$
• 
  A 3-edge-coloring of the Dürer graph or ${\displaystyle G(6,2)}$
• 
  A 3-edge-coloring of the dodecahedron or ${\displaystyle G(10,2)}$
• 
  A 3-edge-coloring of the Desargues graph or ${\displaystyle G(10,3)}$
• 
  A 3-edge-coloring of the Nauru graph or ${\displaystyle 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)
${\displaystyle {\begin{bmatrix}2&1\\1&2\end{bmatrix}}}$	All graphs	All graphs
${\displaystyle {\begin{bmatrix}2&1\\2&1\end{bmatrix}}}$	Just G(3m, 2)	No graphs
${\displaystyle {\begin{bmatrix}1&2\\2&1\end{bmatrix}}}$	No graphs	Just G(2m,3)
${\displaystyle {\begin{bmatrix}0&3\\1&2\end{bmatrix}}}$	No graphs	Just G(4m,3)
${\displaystyle {\begin{bmatrix}0&3\\2&1\end{bmatrix}}}$	Just G(5m,2)	Just G(5m,3)
${\displaystyle {\begin{bmatrix}0&3\\3&0\end{bmatrix}}}$	No graphs	Just G(2m,3)