A permutation on n elements is called a k-derangement (k≤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 σ and τ if στ-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.
© 2013 Mathematical Sciences Publishers
derangements, eulerian, chromatic number, maximal clique, cayley graph, independent set
Jackson, Hannah, Kathryn Nyman, and Les Reid. "Properties of generalized derangement graphs." Involve, a Journal of Mathematics 6, no. 1 (2013): 25-33.
Involve, a Journal of Mathematics