2011/06/27 by Jackson, Hannah, Nyman, Kathryn, Reid, Les
#05A05 #05C45 (secondary) #05C69 (primary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1106.5522
A permutation sigma in Sn is a k-derangement if for any subset X = a1, . . ., ak ⊆ [n], sigma(a1), . . ., sigma(ak) is not equal to X. One can form the k-derangement graph on the set of permutations of Sn 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 number of the 2-derangement graph.