Cospectral graphs and the generalized adjacency matrix Original Research Article

Let 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 image of y. We call such graphs image-cospectral. It follows that image is a rational number, and we prove existence of a pair of image-cospectral graphs for every rational image. In addition, we generate by computer all image-cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of image-cospectral graphs for all rational image, where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of image, and by computer we find all such pairs of image-cospectral graphs on at most eleven vertices.