Transactions of the American Mathematical Society

Author(s): Cai Heng Li
Journal: Trans. Amer. Math. Soc. 358 (2006), 4605-4635.
MSC (2000): Primary 20B15, 20B30, 05C25
Posted: May 9, 2006
Retrieve article in: PDF DVI PostScript

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.

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 -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 -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 , 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

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

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
Email: li@maths.uwa.edu.au

DOI: 10.1090/S0002-9947-06-03900-6
PII: S 0002-9947(06)03900-6
Received by editor(s): April 13, 2004
Received by editor(s) in revised form: October 14, 2004
Posted: 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 of article: Copyright 2006, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS