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)



Analysing finite locally $s$-arc transitive graphs

Authors: Michael Giudici, Cai Heng Li and Cheryl E. Praeger
Journal: Trans. Amer. Math. Soc. 356 (2004), 291-317
MSC (2000): Primary 05C25, 20B25
Published electronically: August 25, 2003
MathSciNet review: 2020034
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new approach to analysing finite graphs which admit a vertex intransitive group of automorphisms $G$ and are either locally $(G,s)$-arc transitive for $s \geq 2$ or $G$-locally primitive. Such graphs are bipartite with the two parts of the bipartition being the orbits of $G$. Given a normal subgroup $N$ which is intransitive on both parts of the bipartition, we show that taking quotients with respect to the orbits of $N$ preserves both local primitivity and local $s$-arc transitivity and leads us to study graphs where $G$ acts faithfully on both orbits and quasiprimitively on at least one. We determine the possible quasiprimitive types for $G$ in these two cases and give new constructions of examples for each possible type. The analysis raises several open problems which are discussed in the final section.

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

  • 1. Robert W. Baddeley, Two-arc transitive graphs and twisted wreath products, J. Algebraic Combin. 2 (1993), 215-237. MR 94h:05037
  • 2. I. Z. Bouwer and D. Z. Djokovic, On regular graphs. III, J. Combinatorial Theory (B) 14 (1973), 268-277. MR 47:4858
  • 3. Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, no. 45, Cambridge University Press, Cambridge, 1999. MR 2001c:20008
  • 4. Marston D. Conder, Cai Heng Li, and Cheryl E. Praeger, On the Weiss conjecture for finite locally primitive graphs, Proc. Edinburgh Math. Soc. 43 (2000), 129-138. MR 2001e:05054
  • 5. J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, Atlas of finite groups, Clarendon Press, Oxford, 1985. MR 88g:20025
  • 6. A. Delgado, D. Goldschmidt, and B. Stellmacher, Groups and graphs: new results and methods, Birkhäuser Verlag, Basel, 1985. MR 88a:05076
  • 7. P. Dembowski, Finite geometries, Springer-Verlag, Berlin, 1968. MR 38:1597
  • 8. Shaofei Du and Dragan Marusic, Biprimitive graphs of smallest order, J. Algebraic Combin. 9 (1999), 151-156. MR 2000b:05069
  • 9. Shaofei Du and Mingyao Xu, A classification of semisymmetric graphs of order $2pq$, Comm. Algebra 28 (2000), 2685-2715. MR 2001g:05059
  • 10. Xin Gui Fang, Cai Heng Li, and Cheryl E. Praeger, On locally two-arc transitive graphs admitting a Ree simple group, in preparation.
  • 11. Jon Folkman, Regular line-symmetric graphs, J. Combinatorial Theory 3 (1967), 215-232. MR 37:97
  • 12. Michael Giudici, Cai Heng Li, and Cheryl E. Praeger, Characterising finite locally $s$-arc transitive graphs with a star normal quotient, in preparation.
  • 13. -, Some locally 3-arc transitive graphs constructed from triality, submitted.
  • 14. David M. Goldschmidt, Automorphisms of trivalent graphs, Ann. of Math. (2) 111 (1980), 377-406. MR 82a:05052
  • 15. A. A. Ivanov and M. E. Iofinova, Biprimitive cubic graphs, Investigations in the algebraic theory of combinatorial objects, Kluwer, 1993, pp. 459-472.
  • 16. A. A. Ivanov and Cheryl E. Praeger, On finite affine 2-arc transitive graphs, Europ. J. Combinatorics 14 (1993), 421-444. MR 94k:05089
  • 17. Cai Heng Li, On finite moufang graphs, in preparation.
  • 18. -, Finite $s$-arc transitive graphs of prime-power order, Bull. London Math. Soc. 33 (2001), 129-137. MR 2002d:05064
  • 19. -, The finite vertex-primitive and vertex-biprimitive $s$-transitive graphs for $s \geq 4$, Trans. Amer. Math. Soc. 353 (2001), 3511-3529. MR 2002c:05084
  • 20. Cai Heng Li, Cheryl E. Praeger, Akshay Venkatesh, and Sanming Zhou, Finite locally-quasiprimitive graphs, Discrete Math. 246 (2002), 197-218. MR 2003c:05110
  • 21. Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, On the O'Nan-Scott Theorem for finite primitive permutation groups, J. Austral. Math. Soc. (A) 44 (1988), 389-396. MR 89a:20002
  • 22. Cheryl E. Praeger, On a reduction theorem for finite, bipartite 2-arc-transitive graphs, Australas J. Comb. 7 (1993), 21-36. MR 93m:05091
  • 23. 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), 227-239. MR 94f:05068
  • 24. Cheryl E. Praeger, Finite quasiprimitive graphs, Surveys in combinatorics, 1997. Proceedings of the 16th British combinatorial conference, London, UK, July 1997 (R. A. Bailey, ed.), Lond. Math. Soc. Lect. Note Ser., no. 241, Cambridge University Press, 1997, pp. 65-85. MR 99b:05076
  • 25. Gert Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426-438. MR 31:91
  • 26. D. H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford (2) 22 (1971), 551-557. MR 48:5926
  • 27. Bernd Stellmacher, Locally $s$-transitive graphs, unpublished.
  • 28. Michio Suzuki, Group theory. I, Springer-Verlag, Berlin, 1982. MR 82k:20001c
  • 29. W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474. MR 9:97g
  • 30. -, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621-624. MR 22:679
  • 31. R. Weiss, $s$-transitive graphs, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), North-Holland, Amsterdam, 1981, pp. 827-847. MR 83b:05071
  • 32. Richard Weiss, The nonexistence of $8$-transitive graphs, Combinatorica 1 (1981), 309-311. MR 84f:05050
  • 33. Richard Weiss, Generalized polygons and $s$-transitive graphs, Finite geometries, buildings, and related topics (Pingree Park, CO, 1988), Oxford Univ. Press, New York, 1990, pp. 95-103. MR 91j:51011

Similar Articles

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

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

Additional Information

Michael Giudici
Affiliation: School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley, Western Australia 6009, Australia

Cai Heng Li
Affiliation: School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley, Western Australia 6009, Australia

Cheryl E. Praeger
Affiliation: School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley, Western Australia 6009, Australia

Received by editor(s): November 22, 2002
Published electronically: August 25, 2003
Additional Notes: This paper forms part of an Australian Research Council large grant project which supported the first author. The second author was supported by an ARC Fellowship
Article copyright: © Copyright 2003 American Mathematical Society