On the average genus of the random graph |
| |
Authors: | Roman Nedela,Martin koviera |
| |
Affiliation: | Roman Nedela,Martin Škoviera |
| |
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. |
| |
Keywords: | |
|
|