Cospectral graphs and the generalized adjacency matrix

Abstract

Let J be the all-ones rnatrix, 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) over cap of (y) over cap. We call such graphs (y) over cap -cospectral. It follows that is a rational number, and we prove existence of a pair of (y) over cap -cospectral graphs for every rational. In addition, we generate by computer all (y) over cap -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of (y) over cap -cospectral graphs for all rational (y) over cap is an element of (0, 1), where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of, and by computer we find all Such pairs of (y) over cap -cospectral graphs on at most eleven vertices. (C) 2006 Elsevier Inc. All rights reserved.