On Arc-Regular Permutation Groups Using Latin Squares
Sònia P. Mansilla
Escola Politècnica Superior de Castelldefels Universitat Politècnica de Catalunya Av. del Canal Olímpic, s/n 08860 Castelldefels Spain
DOI: 10.1007/s10801-005-6277-6
Abstract
For a given a permutation group G, the problem of determining which regular digraphs admit G as an arc-regular group of automorphism is considered. Groups which admit such a representation can be characterized in terms of generating sets satisfying certain properties, and a procedure to manufacture such groups is presented. The technique is based on constructing appropriate factorizations of (smaller) regular line digraphs by means of Latin squares. Using this approach, all possible representations of transitive groups of degree up to seven as arc-regular groups of digraphs of some degree is presented.
Pages: 5–22
Keywords: keywords Cayley digraph; arc-transitive digraph; Latin square
Full Text: PDF
References
1. L. Babai, “Automorphism groups, isomorphism, reconstruction,” in Handbook of Combinatorics, R. Graham, M. Gr\ddot otschel, and L. Lovász (Eds.), Vol. 1-2, Elsevier, Amsterdam, 1995.
2. L. Babai, P.J. Cameron, M. Deza, and N.M. Singhi, “On sharply edge-transitive permutation groups,” J. Algebra 73 (1981), 573-585.
3. R. Bailey, “Latin squares with highly transitive automorphism groups,” J. Austral. Math. Soc. Ser. A 33 (1982), 18-22. MANSILLA
4. J.M. Brunat, Contribució a l'estudi de la simetria de grafs dirigits i les seves aplicacions, PhD thesis, Universitat Polit`ecnica de Catalunya, Barcelona, 1994.
5. P.J. Cameron, “Digraphs admitting sharply edge-transitive automorphism groups,” European J. Combin. 8 (1987), 357-365.
6. A. Cayley, “On Latin squares,” Messenger of Math. European 19 (1890), 135-137.
7. G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd. edition, Chapman & Hall, London, 1996.
8. J.D. Dixon and B. Mortimer, Permutation groups, Springer Verlag, New York, 1996.
9. M.J. Erickson, Introduction to Combinatorics, John Wiley & Sons, Inc., New York, 1996.
10. The GAP Group, GAP-Groups, Algorithms, and Programming, Version 4.2, Aachen, St Andrews, 1999, (http://www-gap.dcs.st-and.ac.uk/\sim gap).
11. R.L. Hemminger and L.W. Beineke, “Line graphs and line digraphs,” in Selected Topics in Graph Theory I, L.W. Beineke and R.J. Wilson (Eds.), Academic Press, London, 1978.
12. S.P. Mansilla and O. Serra, “Construction of k-arc transitive digraphs,” Discrete Math. to appear.
13. S.P. Mansilla and O. Serra, “Automorphism groups of k-arc transitive covers,” Discrete Math. submitted.
14. J. L\ddot utzen, G. Sabidussi, and B. Toft, “Julius Petersen 1839-1910: A biography,” Discrete Math. 100 (1992), 9-82.
15. J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 1992.
2. L. Babai, P.J. Cameron, M. Deza, and N.M. Singhi, “On sharply edge-transitive permutation groups,” J. Algebra 73 (1981), 573-585.
3. R. Bailey, “Latin squares with highly transitive automorphism groups,” J. Austral. Math. Soc. Ser. A 33 (1982), 18-22. MANSILLA
4. J.M. Brunat, Contribució a l'estudi de la simetria de grafs dirigits i les seves aplicacions, PhD thesis, Universitat Polit`ecnica de Catalunya, Barcelona, 1994.
5. P.J. Cameron, “Digraphs admitting sharply edge-transitive automorphism groups,” European J. Combin. 8 (1987), 357-365.
6. A. Cayley, “On Latin squares,” Messenger of Math. European 19 (1890), 135-137.
7. G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd. edition, Chapman & Hall, London, 1996.
8. J.D. Dixon and B. Mortimer, Permutation groups, Springer Verlag, New York, 1996.
9. M.J. Erickson, Introduction to Combinatorics, John Wiley & Sons, Inc., New York, 1996.
10. The GAP Group, GAP-Groups, Algorithms, and Programming, Version 4.2, Aachen, St Andrews, 1999, (http://www-gap.dcs.st-and.ac.uk/\sim gap).
11. R.L. Hemminger and L.W. Beineke, “Line graphs and line digraphs,” in Selected Topics in Graph Theory I, L.W. Beineke and R.J. Wilson (Eds.), Academic Press, London, 1978.
12. S.P. Mansilla and O. Serra, “Construction of k-arc transitive digraphs,” Discrete Math. to appear.
13. S.P. Mansilla and O. Serra, “Automorphism groups of k-arc transitive covers,” Discrete Math. submitted.
14. J. L\ddot utzen, G. Sabidussi, and B. Toft, “Julius Petersen 1839-1910: A biography,” Discrete Math. 100 (1992), 9-82.
15. J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 1992.