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
Recommended Citation
Jackson, Hannah, Kathryn Nyman, and Les Reid. "Properties of generalized derangement graphs." Involve, a Journal of Mathematics 6, no. 1 (2013): 25-33.
Journal Title
Involve, a Journal of Mathematics
