Which generalized petersen graphs are cayley graphs?
Roman Nedela, Martin Škoviera · Journal of Graph Theory · 1995
Abstract The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex‐set {uj; i ϵ Zn} ∪ {vj; i ϵ Zn}, and edge‐set {uiui, uivi, vivi+k, iϵZn}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k2 1 (mod n); and (ii) GP(n, k) is a vertex‐transitive graph that is not a Cayley graph if and only if k2 ‐1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1‐skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n‐dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211‐218]. © 1995 John Wiley & Sons, Inc.