Vol. 6, No. 1, 2013

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Properties of generalized derangement graphs

Hannah Jackson, Kathryn Nyman and Les Reid

Vol. 6 (2013), No. 1, 25–33
Abstract

A permutation on $n$ elements is called a $k$-derangement ($k\le n$) if no $k$-element subset is mapped to itself. One can form the $k$-derangement graph on the set of all permutations on $n$ elements by connecting two permutations $\sigma$ and $\tau$ if $\sigma {\tau }^{-1}$ is a $k$-derangement. We characterize when such a graph is connected or Eulerian. For  $n$ an odd prime power, we determine the independence, clique and chromatic numbers of the 2-derangement graph.

Keywords
derangements, Eulerian, chromatic number, maximal clique, Cayley graph, independent set
Mathematical Subject Classification 2010
Primary: 05C69, 05A05
Secondary: 05C45