Regularity and the generalized adjacency spectra of graphs

For every rational number x ∈ (0, 1), we construct a pair of graphs, one regular and one nonregular with adjacency matrices A1 and A2, having the property that A1 − xJ and A2 − 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.