Brunat, J. M.; Fiol, M. A.; Fiol, M. L. Digraphs on permutations. (English) Zbl 0885.05069 Discrete Math. 174, No. 1-3, 73-86 (1997). “This paper focuses on a family of vertex symmetric digraphs …which were introduced by M. L. Fiol [The relation between digraphs and groups through Cayley digraphs, Universitat Autònoma de Barcelona, 1984 (in Catalan)].” For integers \(k\) and \(n\), \(1\leq k\leq n-1\), a digraph \(P(n,k)\) has as vertices the \(k\)-permutations of \([n]=\{1,2,\dots ,n\}\); vertex \(x_1x_2\dots x_k\) is adjacent to all vertices \(x_2x_3\dots x_kx\) where \(x\in \{x_{k+1},x_{k+2},\dots ,x_n\}\). It is shown that any \(\sigma\in S_n\) induces an automorphism \(f_\sigma\) of \(P(n,k)\) defined by \(f_\sigma(x_1x_2\dots x_k) =x_{\sigma(1)}x_{\sigma(2)}\dots x_{\sigma(k)}\), and that the mapping \(\sigma \mapsto f_\sigma\) is an isomorphism from \(S_n\) to \(\operatorname{Aut} P(n,k)\). The authors characterize those digraphs \(P(n,k)\) which are “Cayley digraphs”. The diameter of \(P(n,k)\) is shown to be \(2k\) when \(n\geq 2k\), and to be \(1+{{k+1}\choose 2}\) if \(n=k+2\). Reviewer: W.G.Brown (Montreal) Cited in 4 Documents MSC: 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments 05A05 Permutations, words, matrices 05C75 Structural characterization of families of graphs Keywords:Cayley colour graph; digraphs PDFBibTeX XMLCite \textit{J. M. Brunat} et al., Discrete Math. 174, No. 1--3, 73--86 (1997; Zbl 0885.05069) Full Text: DOI References: [1] Brunat, J. M., A contribution to the study of the symmetric digraphs and its applications, (Ph.D. Thesis (1994), Universitat Politècnica de Catalunya), (in Catalan) [2] Comellas, F.; Fiol, M. A., Vertex-symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1-11 (1995) · Zbl 0822.05033 [3] Corbett, P. F., Rotator graphs, an efficient topology for point-to-point multiprocessor networks, IEEE Trans. Parallel Distrib. Systems, 3, 622-626 (1992) [4] Faber, V.; Moore, J. W.; Chen, W. Y.C., Cycle prefix digraphs for symmetric interconnexion networks, Networks, 23, 641-649 (1993) · Zbl 0802.90043 [5] Fiol, M. L., The relation between digraphs and groups through Cayley digraphs, (Master Diss. (1984), Universitat Autònoma de Barcelona), (in Catalan) [6] Fiol, M. A.; Yebra, J. L.A.; Alegre, I., Line digraph iterations and the \((d, k)\) digraph problem, IEEE Trans. Comput., C-33, 400-403 (1984) · Zbl 0528.68048 [7] Hemminger, R. L.; Beineke, W. B., Line graphs and line digraphs, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory I (1978), Academic Press: Academic Press London) · Zbl 0434.05056 [8] Passman, D. S., (Permutation Groups (1968), Benjamin: Benjamin New York) [9] Robinson, D. J.S., A Course in the Theory of Groups, (Graduate Texts in Mathematics, vol. 80 (1982), Springer: Springer New York, Verlag) · Zbl 0496.20038 [10] Sabidussi, G., On a class of fixed-point-free graphs, (Proc. Amer. Math. Soc., 9 (1958)), 800-804 · Zbl 0091.37701 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.