Digraphs on permutations (Q1377815)

``This paper focuses on a family of vertex symmetric digraphs \dots which were introduced by \textit{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 \(\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\).