Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph

Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ejc.2013.01.008

Title:	Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
Authors:	Ku, C.Y. Wong, K.B.
Issue Date:	Aug-2013
Citation:	Ku, C.Y., Wong, K.B. (2013-08). Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph. European Journal of Combinatorics 34 (6) : 941-956. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ejc.2013.01.008
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.
Source Title:	European Journal of Combinatorics
URI:	http://scholarbank.nus.edu.sg/handle/10635/104152
ISSN:	01956698
DOI:	10.1016/j.ejc.2013.01.008
Appears in Collections:	Staff Publications

There are no files associated with this item.

Check