Cospectral graphs and the generalized adjacency matrix |
| |
Authors: | E.R. van Dam W.H. Haemers J.H. Koolen |
| |
Affiliation: | a Tilburg University, Department of Econometrics and Operations Research, P.O. Box 90153, 5000 LE Tilburg, The Netherlands b POSTECH, Department of Mathematics, Pohang 790-784, South Korea |
| |
Abstract: | 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 of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , 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 -cospectral graphs on at most eleven vertices. |
| |
Keywords: | 05C50 05E99 |
本文献已被 ScienceDirect 等数据库收录! |
|