Digraphs on permutations
``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\).
- Cycle prefix digraphs for symmetric interconnection networks
- scientific article; zbMATH DE number 3675952 (Why is no real title available?)
- scientific article; zbMATH DE number 3781457 (Why is no real title available?)
- scientific article; zbMATH DE number 3286093 (Why is no real title available?)
- Line Digraph Iterations and the (d, k) Digraph Problem
- On a Class of Fixed-Point-Free Graphs
- Vertex-symmetric digraphs with small diameter
This page was built for publication: Digraphs on permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377815)
