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

Share

COinS