Regularity and the generalized adjacency spectra of graphs

Abstract: For every rational number x ∈(0,1), we construct a pair of graphs, one regular and one nonregular with adjacency matrices A 1 and A2, having the property that A 1 − xJ and A 2 − xJ have the same spectrum (J is the all-ones matrix). This solves a problem of Van Dam and the second author. For some values of x, we have generated the smallest examples (with respect to the number of vertices) by computer. [Copyright &y& Elsevier]