×

Automorphism groups of \(k\)-arc transitive covers. (English) Zbl 1035.05049

Let \(\Gamma=\text{ Cay\,}(G,S)\) be a (strongly connected) Cayley digraph and \((\text{Aut\,} G)_S\) the set of automorphisms \(\alpha\) of \(G\) such that \(S^\alpha=S\). The semidirect product \(G\rtimes (\text{Aut\,} G)_S\) acts on \(G\) in a natural way (\(g^{(h,\alpha)}=hg^\alpha\)) and \(G\rtimes (\text{Aut\,} G)_S\) is a subgroup of \(\text{Aut\,}\Gamma\). The Cayley digraph \(\Gamma\) is said to be normal if \(\text{Aut\,}\Gamma=G\rtimes (\text{Aut\,} G)_S\). Let \(\Gamma=\text{Cay\,}(G,S)\) be \(k\)-arc transitive of degree 2. In the first result of the paper the structure of \(\text{Aut\,}\Gamma\) is described and it is shown that \(\Gamma\) is exactly \(k\)-regular. Moreover, if \(k\leq 1\), then \(\Gamma\) is normal (which is not true for larger values of \(k\)). A \(r\)-regular digraph \(\Gamma=(V,A)\) admits a (\(1\)-)factorization \(\{F_1,\ldots,F_r\}\). Each \(F_i\) corresponds to a permutation \(f_i\) of \(V\). The permutation group generated by \(F=\{f_1,\dots,f_r\}\) is denoted by \(G(\Gamma,F)\). If \(G=G(\Gamma,F)\), the digraph \(\text{ Cay}(G,F)\) is called a Cayley cover of \(\Gamma\). A factorization \(F\) of a \(k\)-line digraph \(\Gamma=L^k\Gamma_0\) such that the resulting Cayley cover is also a \(k\)-line digraph is said to be a \(k\)-uniform factorization. It is shown that every factorization of a connected \(k\)-line digraph of degree 2 with \(k\leq 2\) is uniform. In S. P. Mansilla and O. Serra [Discrete Math. 231, 337–349 (2001; Zbl 0981.05051)] the authors gave a technique to construct \(k\)-arc transitive covers of the complete symmetric digraph with loops \(K_r^+\) and without loops \(K_r\). Here, they have computed all the 2-arc transitive covers of \(K_2^+\) and \(K_3\) which can be obtained using their technique. They give the structure of the group and a number of parameters. Families of Cayley covers of \(K_{r+1}\) and of the Kautz digraph \(K(r,k+1)\) (with \(r+1\) a prime number) are also studied. Finally, they characterize Cayley digraphs which are \(m\)-generalized cycles (i.e. such that there exists a graph homomorphism from \(\Gamma\) onto the cyle of length \(m\)). This result is considered in the context of finding \(k\)-arc transitive digraphs which are not homomorphic to cycles or paths.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0981.05051

Software:

GRAPE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babai, L., Arc transitive covering digraphs and their eigenvalues, J. Graph Theory, 9, 363-370 (1985) · Zbl 0583.05030
[2] Brunat, J. M.; Espona, M.; Fiol, M. A.; Serra, O., Cayley digraphs from complete generalized cycles, European J. Combin., 20, 5, 337-349 (1999) · Zbl 0956.05051
[3] Cameron, P. J.; Praeger, C. E.; Wormald, N. C., Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica, 13, 377-396 (1993) · Zbl 0793.05065
[4] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001
[5] Conder, M.; Lorimer, P.; Praeger, C. E., Constructions for arc-transitive digraphs, J. Austral. Math. Soc. Ser. A, 59, 61-80 (1995) · Zbl 0839.05049
[6] Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A., \(ATLAS\) of Finite Groups (1985), Oxford University Press: Oxford University Press New York · Zbl 0568.20001
[7] Dixon, J. D.; Mortimer, B., Permutation Groups (1996), Springer: Springer Berlin, NY · Zbl 0951.20001
[8] Espona, M.; Serra, O., Cayley digraphs based on the De Bruijn networks, SIAM J. Discrete Math., 11, 305-317 (1998) · Zbl 0916.05028
[9] Fiol. J. L.A. Yebra, M. A.; Alegre, I., Line digraph iterations and the \((d,k)\) digraph problem, IEEE Trans. Comput., C-33, 400-403 (1984) · Zbl 0528.68048
[10] Hamidoune, Y. O., Sur les atomes d’un graphe orienté, C.R. Acad. Sci. Paris A, 284, 1253-1256 (1977) · Zbl 0352.05035
[11] R.L. Hemminger, L.W. Beineke, Line graphs and line digraphs, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory, Vol. I, Academic Press, London, 1978.; R.L. Hemminger, L.W. Beineke, Line graphs and line digraphs, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory, Vol. I, Academic Press, London, 1978. · Zbl 0434.05056
[12] A. Malnič, D. Marušič, N. Seifter, B. Zgrablić, Highly arc-transitive digraphs with no homomorphism onto the two-way infinite path, preprint.; A. Malnič, D. Marušič, N. Seifter, B. Zgrablić, Highly arc-transitive digraphs with no homomorphism onto the two-way infinite path, preprint. · Zbl 1012.05080
[13] Mansilla, S. P.; Serra, O., Construction of \(k\)-arc transitive digraphs, Discrete Math., 231, 337-349 (2001) · Zbl 0981.05051
[14] Praeger, C. E., Highly arc transitive digraphs, European J. Combin., 10, 281-292 (1989) · Zbl 0677.05041
[15] Praeger, C. E., On homomorphic images of edge-transitive directed graphs, Australas. J. Combin., 3, 207-210 (1991) · Zbl 0758.05055
[16] Soicher, L. H., GRAPE: a system for computing with graphs and groups, (Finkelstein, Larry; M. Kantor, William, Groups and Computation. Groups and Computation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 11 (1993), American Mathematical Society: American Mathematical Society Providence, RI), 287-291 · Zbl 0833.05071
[17] Tutte, W. T., On the symmetry of cubic graphs, Canad. J. Math., 11, 621-624 (1959) · Zbl 0093.37701
[18] Weiss, R., The nonexistence of 8-transitive graphs, Combinatorica, 1, 309-311 (1981) · Zbl 0486.05032
[19] Xu, M. Y., Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math., 182, 309-319 (1998) · Zbl 0887.05025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.