Properties of Generalized Derangement Graphs

Details Properties of Generalized Derangement Graphs Properties of Generalized Derangement Graphs

2011-06-27

arxiv.org/abs/1106.5522v1

Mathematics

Combinatorics

8 pages, 1 figure

Scientific paper

A permutation sigma in Sn is a k-derangement if for any subset X = {a1, . . ., ak} \subseteq [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.

Affiliated with

Also associated with

No associations

Rating

Properties of Generalized Derangement Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Properties of Generalized Derangement Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properties of Generalized Derangement Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-40519