The Structure of Automorphism Groups of Cayley Graphs and Maps
Robert Jajcay
DOI: 10.1023/A:1008763602097
Abstract
The automorphism groups Aut( C( G, X)) and Aut( CM( G, X, p)) of a Cayley graph C( G, X) and a Cayley map CM( G, X, p) both contain an isomorphic copy of the underlying group G acting via left translations. In our paper, we show that both automorphism groups are rotary extensions of the group G by the stabilizer subgroup of the vertex 1 G . We use this description to derive necessary and sufficient conditions to be satisfied by a finite group in order to be the (full) automorphism group of a Cayley graph or map and classify all the finite groups that can be represented as the (full) automorphism group of some Cayley graph or map.
Pages: 73–84
Keywords: Cayley graph; Cayley map; automorphism group
Full Text: PDF
References
1. N. Biggs, “Cayley maps and symmetrical maps,” Proc. Camb. Phil. Soc. 72 (1972), 381-386.
2. N. Biggs and A.T. White, “Permutation groups and combinatorial structures,” Math. Soc. Lect. Notes, vol. 33, Cambridge Univ. Press, Cambridge, 1979.
3. C.D. Godsil, “GRR's for non-solvable groups,” Algebraic methods in graph theory, Vol. I., II. (Szeged, 1978), 221-239.
4. J. Gross and T. Tucker, Topological Graph Theory, John Wiley & Sons, New York, 1987.
5. W. Imrich and M.E. Watkins, “On graphical regular representations of cyclic extensions of groups,” Pac. J. Math. 55 (1974), 461-477.
6. R. Jajcay, “Automorphism groups of Cayley maps,” Journal of Comb. Theory Series B 59 (1993), 297-310.
7. R. Jajcay, “On a new product of groups,” Europ. J. Combinatorics 15 (1994), 251-252.
8. R. Jajcay, “Characterization and construction of Cayley graphs admitting regular Cayley maps,” Discrete Mathematics 158 (1996), 151-160.
9. R. Jajcay, “On a construction of infinite families of regular Cayley maps,” Combinatorica 18(2) (1998), 191-199.
10. L.D. James and G.A. Jones, “Regular orientable imbeddings of complete graphs,” Journal of Comb. Theory 39 (1985), 353-367.
11. G.A. Jones and D. Singerman, “Theory of maps on orientable surfaces,” Proc. London Math. Soc. 37(3) (1978), 273-307.
12. L.A. Nowitz and M.E. Watkins, “Graphical regular representations of non-abelian groups, I,” Canadian J. Math. 24 (1972), 993-1008.
13. L.A. Nowitz and M.E. Watkins, “Graphical regular representations of non-abelian groups, II,” Canadian J. Math. 24 (1972), 1009-1018.
14. L.V. Sabinin, “On the equivalence of categories of loops and homogeneous spaces,” Soviet Math. Dokl. 13(4) (1972), 970-974.
15. M. \check Skoviera and J. \check Sirá\check n, “Regular maps from Cayley graphs, Part I. Balanced Cayley maps,” Discrete Math. 109 (1992), 265-276.
16. M. \check Skoviera and J. \check Sirá\check n, “Regular maps from Cayley graphs II. Antibalanced Cayley maps,” Discrete Math. 124 (1994), 179-191.
17. A.T. White, Strongly Symmetric Maps, Graph Theory and Combinatorics, R.J. Wilson (Ed.), Pitman, London, 1979, 106-132.
18. H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.
2. N. Biggs and A.T. White, “Permutation groups and combinatorial structures,” Math. Soc. Lect. Notes, vol. 33, Cambridge Univ. Press, Cambridge, 1979.
3. C.D. Godsil, “GRR's for non-solvable groups,” Algebraic methods in graph theory, Vol. I., II. (Szeged, 1978), 221-239.
4. J. Gross and T. Tucker, Topological Graph Theory, John Wiley & Sons, New York, 1987.
5. W. Imrich and M.E. Watkins, “On graphical regular representations of cyclic extensions of groups,” Pac. J. Math. 55 (1974), 461-477.
6. R. Jajcay, “Automorphism groups of Cayley maps,” Journal of Comb. Theory Series B 59 (1993), 297-310.
7. R. Jajcay, “On a new product of groups,” Europ. J. Combinatorics 15 (1994), 251-252.
8. R. Jajcay, “Characterization and construction of Cayley graphs admitting regular Cayley maps,” Discrete Mathematics 158 (1996), 151-160.
9. R. Jajcay, “On a construction of infinite families of regular Cayley maps,” Combinatorica 18(2) (1998), 191-199.
10. L.D. James and G.A. Jones, “Regular orientable imbeddings of complete graphs,” Journal of Comb. Theory 39 (1985), 353-367.
11. G.A. Jones and D. Singerman, “Theory of maps on orientable surfaces,” Proc. London Math. Soc. 37(3) (1978), 273-307.
12. L.A. Nowitz and M.E. Watkins, “Graphical regular representations of non-abelian groups, I,” Canadian J. Math. 24 (1972), 993-1008.
13. L.A. Nowitz and M.E. Watkins, “Graphical regular representations of non-abelian groups, II,” Canadian J. Math. 24 (1972), 1009-1018.
14. L.V. Sabinin, “On the equivalence of categories of loops and homogeneous spaces,” Soviet Math. Dokl. 13(4) (1972), 970-974.
15. M. \check Skoviera and J. \check Sirá\check n, “Regular maps from Cayley graphs, Part I. Balanced Cayley maps,” Discrete Math. 109 (1992), 265-276.
16. M. \check Skoviera and J. \check Sirá\check n, “Regular maps from Cayley graphs II. Antibalanced Cayley maps,” Discrete Math. 124 (1994), 179-191.
17. A.T. White, Strongly Symmetric Maps, Graph Theory and Combinatorics, R.J. Wilson (Ed.), Pitman, London, 1979, 106-132.
18. H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.