Cospectral graphs and the generalized adjacency matrix

AbstractLet J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ−A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ−A for exactly one value yˆ of y. We call such graphs yˆ-cospectral. It follows that yˆ is a rational number, and we prove existence of a pair of yˆ-cospectral graphs for every rational yˆ. In addition, we generate by computer all yˆ-cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of yˆ-cospectral graphs for all rational yˆ∈(0,1), where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of yˆ, and by computer we find all such pairs of yˆ-cospectral graphs on at most eleven vertices