Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
Ku, C.Y. Wong, K.B.
Wong, K.B.
Citations
Altmetric:
Alternative Title
Abstract
We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition with a fixed first part decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales [C.Y. Ku, D.B. Wales, Eigenvalues of the derangement graph, J. Combin. Theory Ser. A 117 (2010) 289-312] regarding the lower and upper bounds for the absolute values of these eigenvalues. © 2013 Elsevier Ltd.
Keywords
Source Title
European Journal of Combinatorics
Publisher
Series/Report No.
Collections
Rights
Date
2013-08
DOI
10.1016/j.ejc.2013.01.008
Type
Article