The spectrum of eigenvalues for certain subgraphs of the k-point fixing graph

Abstract

Let Sn be the symmetric group on n-points. The k-point fixing graph F(n, k) is defined to be the graph with vertex set Sn and two vertices g, h of F(n, k) are joined if and only if gh−1 fixes exactly k points. In this paper, we give a recurrence formula for the eigenvalues of a class of regular subgraphs of F(n, k). By using this recurrence formula, we will determine the smallest eigenvalues for this class of regular subgraphs of F(n, 1) for sufficiently large n.