JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 29, No 1 (2009)

Cai Heng Li , Tian Khoon Lim and Cheryl E. Praeger

University of Western Australia School of Mathematics and Statistics 35 Stirling Highway Crawley WA 6009 Australia

A factorisation of a complete graph K _n is a partition of its edges with each part corresponding to a spanning subgraph (not necessarily connected), called a factor. A factorisation is called homogeneous if there are subgroups M< G\leq  S _n such that M is vertex-transitive and fixes each factor setwise, and G permutes the factors transitively. We classify the homogeneous factorisations of K _n for which there are such subgroups G, M with M transitive on the edges of a factor as well as the vertices. We give infinitely many new examples.

1. Alspach, B., Morris, J., Vilfred, V.: Self-complementary circulant graphs. Ars Combinatoria 53, 187- 191 (1999)
2. Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)
3. Bonisoli, A., Buratti, M., Mazzuoccolo, G.: Doubly transitive 2-factorizations. J. Combin. Designs 15(2), 120-132 (2007)
4. Bonisoli, A., Labbate, D.: One-factorizations of complete graphs with vertex-regular automorphism groups. J. Combin. Designs 10(1), 1-16 (2002)
5. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance Regular Graphs. Springer, Berlin (1989)
6. Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. London Math. Soc. 13, 1-22 (1981)
7. Cameron, P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge (1994)
8. Cannon, J., Playoust, C.: An Introduction to Magma. School of Mathematics and Statistics, University of Sydney. (See also )
9. Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, New York (1996)
10. Foulser, D.A.: The flag-transitive collineation group of the finite Desarguesian affine planes. Canad. J. Math. 16, 443-472 (1964)
11. Foulser, D.A., Kallaher, M.J.: Solvable, flag-transitive, rank 3 collineation groups. Geom. Ded. 7, 111-130 (1978)
12. Giudici, M., Li, C.H., Poto\check cnik, P., Praeger, C.E.: Homogeneous factorisations of graphs and digraphs. European J. Combin. 27, 11-37 (2006)
13. Harary, F., Robinson, R.W., Wormald, N.C.: Isomorphic factorisations I: Complete graphs. Trans. Amer. Math. Soc. 242, 243-260 (1978)
14. Harary, F., Robinson, R.W.: Isomorphic factorisations X: Unsolved problems. J. Graph Theory 9, 67-86 (1985)
15. Huppert, B.: Endliche Gruppen I. Springer, Berlin (1967)
16. Huppert, B., Blackburn, N.: Finite Groups III. Springer, Berlin (1982)
17. Jajcay, R., Li, C.H.: Constructions of self-complementary circulants with no multiplicative isomorphisms. European J. Combin. 22, 1093-1100 (2001)
18. Kantor, W.M.: Automorphism groups of designs. Math. Z. 109, 246-252 (1969)
19. Kantor, W.M.: Homogeneous designs and geometric lattices. J. Combin. Theory Ser. A 38, 66-74 (1985)
20. Li, C.H.: On self-complementary vertex-transitive graphs. Comm. Algebra 25, 3903-3908 (1997)
21. Li, C.H., Praeger, C.E.: On partitioning the orbitals of a transitive permutation group. Trans. Amer. Math. Soc. 355, 637-653 (2003)
22. Liebeck, M.W.: The affine permutation groups of rank
3. Proc. London Math. Soc. 54, 477-516 (1987)
23. Lim, T.K.: Arc-transitive homogeneous factorizations and affine planes. J. Combin. Designs 14, 290- 300 (2008)
24. Lim, T.K.: Edge-transitive homogeneous factorisations of complete graphs. PhD thesis, University of Western Australia (2004). (
25. Lim, T.K., Praeger, C.E.: On generalised Paley graphs and their automorphism groups. Mich. Math. J. (2008, to appear)
26. Muzychuk, M.: On Sylow's subgraphs of vertex-transitive self-complementary graphs. Bull. London Math. Soc. 31, 531-533 (1999)
27. Peisert, W.: All self-complementary symmetric graphs. J. Algebra 240, 209-229 (2001)
28. Praeger, C.E.: Finite transitive permutation groups and finite vertex-transitive graphs. In: Graph Symmetry (Montrael, PQ, 1996). Kluwer Academic, Dordrecht (1997)
29. Sibley, T.Q.: On classifying finite edge colored graphs with two transitive automorphism groups.