Abstract

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.

Department(s)

Mathematics

Document Type

Article

DOI

https://doi.org/10.2140/involve.2013.6.25

Rights Information

© 2013 Mathematical Sciences Publishers

Keywords

derangements, eulerian, chromatic number, maximal clique, cayley graph, independent set

Publication Date

2013

Journal Title

Involve, a Journal of Mathematics

Download

Share

COinS