Cospectral Graphs and the Generalized Adjacency Matrix

By E. V. Dam, Willem H. Haemers, Jack H. Koolen. 2007

47 citations recorded by the source corpus.

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

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/020396e618956f8633e2ca389824cf05a6644dd0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. Andries E. Brouwer
  2. Willem H. Haemers
  3. Sebastian M. Cioaba
  4. Dragos M. Cvetkovic
  5. David A. Gregory
  6. Slobodan K. Simic

In Discrete Mathematics and Combinatorics

  1. Andries E. Brouwer
  2. Willem H. Haemers

In Geometry and Topology

  1. Andries E. Brouwer
  2. Willem H. Haemers
  3. Sebastian M. Cioaba
  4. Dragos M. Cvetkovic
  5. David A. Gregory
  6. Slobodan K. Simic

Citations in the corpus