Finite edge-transitive Cayley graphs and rotary Cayley maps

Li, Cai

doi:10.1090/S0002-9947-06-03900-6

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