Finite edge-transitive Cayley graphs and rotary Cayley maps
HTML articles powered by AMS MathViewer
- by Cai Heng Li PDF
- Trans. Amer. Math. Soc. 358 (2006), 4605-4635 Request permission
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
- Norman Biggs, Cayley maps and symmetrical maps, Proc. Cambridge Philos. Soc. 72 (1972), 381–386. MR 302482, DOI 10.1017/s0305004100047216
- Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140
- N. L. Biggs and A. T. White, Permutation groups and combinatorial structures, London Mathematical Society Lecture Note Series, vol. 33, Cambridge University Press, Cambridge-New York, 1979. MR 540889, DOI 10.1017/CBO9780511600739
- Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031, DOI 10.1017/CBO9780511623677
- Yu Qing Chen and Cai Heng Li, Relative difference sets fixed by inversion and Cayley graphs, J. Combin. Theory Ser. A 111 (2005), no. 1, 165–173. MR 2144861, DOI 10.1016/j.jcta.2004.09.007
- M. Conder, On symmetries of Cayley graphs and the graphs underlying regular maps, in preparation.
- Marston Conder and Brent Everitt, Regular maps on non-orientable surfaces, Geom. Dedicata 56 (1995), no. 2, 209–219. MR 1338960, DOI 10.1007/BF01267644
- M. Conder, R. Jajcay and T. Tucker, Regular Cayley maps for finite abelian groups, preprint (2003).
- J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, $\Bbb {ATLAS}$ of finite groups, Oxford University Press, Eynsham, 1985. Maximal subgroups and ordinary characters for simple groups; With computational assistance from J. G. Thackray. MR 827219
- Xin Gui Fang, Cai Heng Li, and Ming Yao Xu, On edge-transitive Cayley graphs of valency four, European J. Combin. 25 (2004), no. 7, 1107–1116. MR 2083459, DOI 10.1016/j.ejc.2003.07.008
- Walter Feit, Some consequences of the classification of finite simple groups, The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979) Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R.I., 1980, pp. 175–181. MR 604576
- A. Gardiner, R. Nedela, J. Širáň, 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, DOI 10.1112/S0024610798006851
- C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), no. 3, 243–256. MR 637829, DOI 10.1007/BF02579330
- B. Huppert, Finite Groups, (Springer-Verlag, Berlin, 1967).
- Noboru Itô, Über das Produkt von zwei abelschen Gruppen, Math. Z. 62 (1955), 400–401 (German). MR 71426, DOI 10.1007/BF01180647
- Robert Jajcay and Jozef Širáň, A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994), 105–114. MR 1296944
- Gareth A. Jones, Cyclic regular subgroups of primitive permutation groups, J. Group Theory 5 (2002), no. 4, 403–407. MR 1931365, DOI 10.1515/jgth.2002.011
- Cai Heng Li, Finite CI-groups are soluble, Bull. London Math. Soc. 31 (1999), no. 4, 419–423. MR 1687493, DOI 10.1112/S0024609399005901
- Cai Heng Li, Finite $s$-arc transitive graphs of prime-power order, Bull. London Math. Soc. 33 (2001), no. 2, 129–137. MR 1815416, DOI 10.1112/blms/33.2.129
- Cai Heng Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Math. 256 (2002), no. 1-2, 301–334. MR 1927074, DOI 10.1016/S0012-365X(01)00438-1
- Cai Heng Li, The finite primitive permutation groups containing an abelian regular subgroup, Proc. London Math. Soc. (3) 87 (2003), no. 3, 725–747. MR 2005881, DOI 10.1112/S0024611503014266
- Cai Heng Li, Finite $s$-arc transitive Cayley graphs and flag-transitive projective planes, Proc. Amer. Math. Soc. 133 (2005), no. 1, 31–41. MR 2085150, DOI 10.1090/S0002-9939-04-07549-5
- C. H. Li, Finite edge-transitive Cayley graphs and rotary Cayley maps, II, in preparation.
- Cai Heng Li, Zai Ping Lu, and Dragan Marušič, On primitive permutation groups with small suborbits and their orbital graphs, J. Algebra 279 (2004), no. 2, 749–770. MR 2078940, DOI 10.1016/j.jalgebra.2004.03.005
- Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, The maximal factorizations of the finite simple groups and their automorphism groups, Mem. Amer. Math. Soc. 86 (1990), no. 432, iv+151. MR 1016353, DOI 10.1090/memo/0432
- Martin W. Liebeck and Aner Shalev, Classical groups, probabilistic methods, and the $(2,3)$-generation problem, Ann. of Math. (2) 144 (1996), no. 1, 77–125. MR 1405944, DOI 10.2307/2118584
- Gunter Malle, Jan Saxl, and Thomas Weigel, Generation of classical groups, Geom. Dedicata 49 (1994), no. 1, 85–116. MR 1261575, DOI 10.1007/BF01263536
- Dragan Marušič and Roman Nedela, Maps and half-transitive graphs of valency $4$, European J. Combin. 19 (1998), no. 3, 345–354. MR 1621025, DOI 10.1006/eujc.1998.0187
- 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).
- Cheryl E. Praeger, The inclusion problem for finite primitive permutation groups, Proc. London Math. Soc. (3) 60 (1990), no. 1, 68–88. MR 1023805, DOI 10.1112/plms/s3-60.1.68
- Cheryl E. Praeger, An O’Nan-Scott theorem for finite quasiprimitive permutation groups and an application to $2$-arc transitive graphs, J. London Math. Soc. (2) 47 (1993), no. 2, 227–239. MR 1207945, DOI 10.1112/jlms/s2-47.2.227
- Cheryl E. Praeger, Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc. 60 (1999), no. 2, 207–220. MR 1711938, DOI 10.1017/S0004972700036340
- R. Bruce Richter, Jozef Širáň, Robert Jajcay, Thomas W. Tucker, and Mark E. Watkins, Cayley maps, J. Combin. Theory Ser. B 95 (2005), no. 2, 189–245. MR 2171363, DOI 10.1016/j.jctb.2005.04.007
- Martin Škoviera and Jozef Širáň, Regular maps from Cayley graphs. I. Balanced Cayley maps, Discrete Math. 109 (1992), no. 1-3, 265–276. Algebraic graph theory (Leibnitz, 1989). MR 1192388, DOI 10.1016/0012-365X(92)90296-R
- Jozef Širáň and Martin Škoviera, Regular maps from Cayley graphs. II. Antibalanced Cayley maps, Discrete Math. 124 (1994), no. 1-3, 179–191. Graphs and combinatorics (Qawra, 1990). MR 1258853, DOI 10.1016/0012-365X(94)90089-2
- Helmut Wielandt, Finite permutation groups, Academic Press, New York-London, 1964. Translated from the German by R. Bercov. MR 0183775
- Ming-Yao Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), no. 1-3, 309–319. Graph theory (Lake Bled, 1995). MR 1603719, DOI 10.1016/S0012-365X(97)00152-0
- Shang Jin Xu, Xin Gui Fang, Jie Wang, and Ming Yao Xu, On cubic $s$-arc transitive Cayley graphs of finite simple groups, European J. Combin. 26 (2005), no. 1, 133–143. MR 2101041, DOI 10.1016/j.ejc.2003.10.015
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
- MR Author ID: 305568
- Email: li@maths.uwa.edu.au
- 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.
- © Copyright 2006 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 358 (2006), 4605-4635
- MSC (2000): Primary 20B15, 20B30, 05C25
- DOI: https://doi.org/10.1090/S0002-9947-06-03900-6
- MathSciNet review: 2231390