Cayley Graph on Symmetric Group Generated by Elements Fixing $k$ Points

Abstract

Let ${\mathcal{S}}_n$ be the symmetric group on $[n]=\{1,\dots ,n\}$. The $k$-point fixing graph $\mathcal{F}(n,k)$ is defined to be the graph with vertex set ${\mathcal{S}}_n$ and two vertices $g$, $h$ of $\mathcal{F}(n,k)$ are joined if and only if $g{h}^{-1}$ fixes exactly $k$ points. In this paper, we derive a recurrence formula for the eigenvalues of $\mathcal{F}(n,k)$. Then we apply our result to determine the sign of the eigenvalues of $\mathcal{F}(n,1)$.

22 pages