Which generalized petersen graphs are cayley graphs?

✍ Scribed by Roman Nedela; Martin Škoviera

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 572 KB
• Volume: 19
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190190102

✦ Synopsis

Abstract

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex‐set {u~j~; i ϵ Z~n~} ∪ {v~j~; i ϵ Z~n~}, and edge‐set {u~i~u~i~, u~i~v~i~, v~i~v~i+k, iϵ~Z~n~}. In the paper we prove that

(i) GP(n, k) is a Cayley graph if and only if k^2^  1 (mod n); and

(ii) GP(n, k) is a vertex‐transitive graph that is not a Cayley graph if and only if k^2^  ‐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.