Recent Issues
Volume 18, 1 issue
Volume 17, 5 issues
Volume 17
Issue 5, 723–899
Issue 4, 543–722
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182
Volume 16, 5 issues
Volume 16
Issue 5, 727–903
Issue 4, 547–726
Issue 3, 365–546
Issue 2, 183–364
Issue 1, 1–182
Volume 15, 5 issues
Volume 15
Issue 5, 727–906
Issue 4, 547–726
Issue 3, 367–546
Issue 2, 185–365
Issue 1, 1–184
Volume 14, 5 issues
Volume 14
Issue 5, 723–905
Issue 4, 541–721
Issue 3, 361–540
Issue 2, 181–360
Issue 1, 1–179
Volume 13, 5 issues
Volume 13
Issue 5, 721–900
Issue 4, 541–719
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180
Volume 12, 8 issues
Volume 12
Issue 8, 1261–1439
Issue 7, 1081–1260
Issue 6, 901–1080
Issue 5, 721–899
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180
Volume 11, 5 issues
Volume 11
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179
Volume 10, 5 issues
Volume 10
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180
Volume 9, 5 issues
Volume 9
Issue 5, 721–899
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–180
Volume 8, 5 issues
Volume 8
Issue 5, 721–900
Issue 4, 541–719
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179
Volume 7, 6 issues
Volume 7
Issue 6, 713–822
Issue 5, 585–712
Issue 4, 431–583
Issue 3, 245–430
Issue 2, 125–244
Issue 1, 1–124
Volume 6, 4 issues
Volume 6
Issue 4, 383–510
Issue 3, 261–381
Issue 2, 127–260
Issue 1, 1–126
Volume 5, 4 issues
Volume 5
Issue 4, 379–504
Issue 3, 237–378
Issue 2, 115–236
Issue 1, 1–113
Volume 4, 4 issues
Volume 4
Issue 4, 307–416
Issue 3, 203–305
Issue 2, 103–202
Issue 1, 1–102
Volume 3, 4 issues
Volume 3
Issue 4, 349–474
Issue 3, 241–347
Issue 2, 129–240
Issue 1, 1–127
Volume 2, 5 issues
Volume 2
Issue 5, 495–628
Issue 4, 371–494
Issue 3, 249–370
Issue 2, 121–247
Issue 1, 1–120
Volume 1, 2 issues
Volume 1
Issue 2, 123–233
Issue 1, 1–121
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.
Keywords
derangements, Eulerian, chromatic number, maximal clique,
Cayley graph, independent set
Mathematical Subject Classification 2010
Primary: 05C69, 05A05
Secondary: 05C45
Milestones
Received: 14 September 2011
Revised: 22 May 2012
Accepted: 13 July 2012
Published: 23 June 2013
Communicated by Ann Trenk