Edge pancyclic derangement graphs

Abstract

We consider the derangement graph in which the vertices are permutations of $\{1,\dots ,n\}$. Two vertices are joined by an edge if the corresponding permutations differ in every position. The derangement graph is known to be Hamiltonian and Hamilton-connected. In this note, we show that the derangement graph is edge pancyclic if $n\ge 4$.

7 pages, 1 figure