Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Finite edge-transitive Cayley graphs and rotary Cayley maps

Author: Cai Heng Li
Journal: Trans. Amer. Math. Soc. 358 (2006), 4605-4635
MSC (2000): Primary 20B15, 20B30, 05C25
Published electronically: May 9, 2006
MathSciNet review: 2231390
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper aims to develop a theory for studying Cayley graphs, especially for those with a high degree of symmetry. The theory consists of analysing several types of basic Cayley graphs (normal, bi-normal, and core-free), and analysing several operations of Cayley graphs (core quotient, normal quotient, and imprimitive quotient). It provides methods for constructing and characterising various combinatorial objects, such as half-transitive graphs, (orientable and non-orientable) regular Cayley maps, vertex-transitive non-Cayley graphs, and permutation groups containing certain regular subgroups.

In particular, a characterisation is given of locally primitive holomorph Cayley graphs, and a classification is given of rotary Cayley maps of simple groups. Also a complete classification is given of primitive permutation groups that contain a regular dihedral subgroup.

References [Enhancements On Off] (What's this?)

  • 1. N. Biggs, Cayley maps and symmetrical maps, Proc. Camb. Phil. Soc. 72 (1972), 381-386. MR 0302482 (46:1626)
  • 2. N. Biggs, Algebraic Graph Theory, Cambridge University Press, 2nd ed, 1993, New York. MR 1271140 (95h:05105)
  • 3. N. Biggs and A. T. White, Permutation groups and Combinatorial Structures, London Math. Soc. Lect. Notes 33 (Cambridge Univ. Press, Cambridge 1997). MR 0540889 (80k:20005)
  • 4. P. J. Cameron, Permutation groups, London Mathematical Society Student Texts, 45. Cambridge University Press, Cambridge, 1999. x+220 pp. MR 1721031 (2001c:20008)
  • 5. Y. Q. Chen and C. H. Li, Relative difference sets fixed by inversion and Cayley graphs, J. Combin. Theory Ser. A 111 (2005), 165-173. MR 2144861 (2006b:05059)
  • 6. M. Conder, On symmetries of Cayley graphs and the graphs underlying regular maps, in preparation.
  • 7. M. Conder and B. Everitt, Regular maps on non-orientable surfaces, Geom. Dedicata 56 (1995), no. 2, 209-219. MR 1338960 (96g:05046)
  • 8. M. Conder, R. Jajcay and T. Tucker, Regular Cayley maps for finite abelian groups, preprint (2003).
  • 9. J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, Atlas of Finite Groups, Oxford Univ. Press, London/New York, 1985. MR 0827219 (88g:20025)
  • 10. X. G. Fang, C. H. Li and M. Y. Xu, On edge-transitive Cayley graphs of valency four, European J. Combin. 25 (2004), 1107-1116. MR 2083459
  • 11. W. Feit, Some consequences of the classification of finite simple groups, The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979), 175-181, Proc. Sympos. Pure Math., 37, Amer. Math. Soc., Providence, R.I., 1980. MR 0604576 (82c:20019)
  • 12. A. Gardiner, R. Nedela, J. Širán and M. Škoviera, Characterisation of graphs which underlie regular maps on closed surfaces J. London Math. Soc. (2) 59 (1999), no. 1, 100-108. MR 1688492 (2000a:05104)
  • 13. C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243-256. MR 0637829 (83a:05066)
  • 14. B. Huppert, Finite Groups, (Springer-Verlag, Berlin, 1967).
  • 15. N. Itô, Über das Produkt von zwei abelschen Gruppen, Math. Z. 62 (1955), 400-401. MR 0071426 (17:125b)
  • 16. R. Jajcay and J. Siran, A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994), 105-114. MR 1296944 (95f:05055)
  • 17. G. Jones, Cyclic regular subgroups of primitive permutation groups J. Group Theory 5 (2002), no. 4, 403-407. MR 1931365 (2003h:20004)
  • 18. C. H. Li, Finite CI-groups are soluble, Bull. London Math. Soc. 31 (1999), 419-423. MR 1687493 (2000d:05056)
  • 19. C. H. Li, Finite s-arc transitive graphs of prime-power order, Bull. London Math. Soc. 33 (2001), 129-137. MR 1815416 (2002d:05064)
  • 20. C. H. Li, On isomorphisms of finite Cayley graphs - a survey, Discrete Math. 256 (2002), 301-334. MR 1927074 (2003i:05067)
  • 21. C. H. Li, The finite primitive permutation groups containing an abelian regular subgroup, Proc. London Math. Soc. 87 (2003), 725-748. MR 2005881 (2004i:20003)
  • 22. C. H. Li, Finite $ s$-arc transitive Cayley graphs and flag-transitive projective planes, Proc. Amer. Math. Soc. 133 (2004), 31-41. MR 2085150 (2005g:20003)
  • 23. C. H. Li, Finite edge-transitive Cayley graphs and rotary Cayley maps, II, in preparation.
  • 24. C. H. Li, Z. P. Lu and D. Marušic, Finite primitive permutation groups with a small suborbit and their orbital graphs. J. Algebra 279 (2004), 749-770. MR 2078940 (2005d:20003)
  • 25. M. Liebeck, C. E. Praeger and J. Saxl, The maximal factorizations of the finite simple groups and their automorphism groups, Mem. Amer. Math. Soc. 86 (1990), no. 432, iv+151 pp. MR 1016353 (90k:20048)
  • 26. M. Liebeck and A. Shalev, Classical groups, probabilistic methods, and the $ (2,3)$-generation problem, Ann. Math. 144 (1996), 77-125. MR 1405944 (97e:20106a)
  • 27. G. Malle, J. Saxl and T. Weigel, Generation of classical groups, Geom. Dedicata 49 (1994), 85-116. MR 1261575 (95c:20068)
  • 28. D. Marušic and R. Nedela, Maps and half-transitive graphs of valency $ 4$, European J. Combin. 19 (1998), 345-354. MR 1621025 (99e:05069)
  • 29. P. Neumann, Helmut Wielandt on Permutation groups, in Helmut Wielandt: Mathmatical Works, Eds by B. Huppert and H. Schneider, pp. 3-20, (Berlin, New York, 1994).
  • 30. C. E. Praeger, The inclusion problem for finite primitive permutation groups, Proc. London Math. Soc. (3) 60 (1990), 68-88. MR 1023805 (90j:20009)
  • 31. C. E. Praeger, An O'Nan-Scott theorem for finite quasiprimitive permutation groups and an application to 2-arc transitive graphs, J. London. Math. Soc. 47 (1992), 227-239. MR 1207945 (94f:05068)
  • 32. C. E. Praeger, Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc. 60 (1999), 207-220. MR 1711938 (2000j:05057)
  • 33. B. Richter, J. Širán, R. Jajcay, T. Tuker and M. Watkins, Cayley maps, J. Combin. Theory Ser. B 95 (2005), 189-245. MR 2171363
  • 34. M. Škoviera and J. Širán, Regular maps from Cayley graphs. I. Balanced Cayley maps, Discrete Math. 109 (1992), 265-276. MR 1192388 (93k:05055)
  • 35. J. Širán and M. Škoviera, Regular maps from Cayley graphs. II. Antibalanced Cayley maps, Discrete Math. 124 (1994), no. 1-3, 179-191. MR 1258853 (94m:05069)
  • 36. H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964. MR 0183775 (32:1252)
  • 37. M. Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-320. MR 1603719 (98i:05096)
  • 38. S. J. Xu, X. G. Fang, J. Wang and M. Y. Xu, On cubic s-arc transitive Cayley graphs of finite simple groups, Europ. J. Combin. 26 (2005), 133-143. MR 2101041

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20B15, 20B30, 05C25

Retrieve articles in all journals with MSC (2000): 20B15, 20B30, 05C25

Additional Information

Cai Heng Li
Affiliation: School of Mathematics and Statistics, University of Western Australia, Crawley, 6009 WA, Australia – and – Department of Mathematics, Yunnan University, Kunming 650031, People’s Republic of China

Received by editor(s): April 13, 2004
Received by editor(s) in revised form: October 14, 2004
Published electronically: May 9, 2006
Additional Notes: Part of this work was done while the author held a QEII Fellowship from the Australian Research Council. The author is grateful to the referee for constructive suggestions.
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society