Graph Cospectrality using Neighborhood Matrices

  • Aline Duarte Bessa
  • Ivan Carmo Rocha-Neto
  • Suani Tavares Rubim de Pinho
  • Roberto Fernandes Silva Andrade
  • Thierry Correa Petit Lobao
Keywords: graph theory, cospectrality, neighborhood


In this note we address the problem of graph isomorphism by means of eigenvalue spectra of different matrix representations:  the neighborhood matrix $\hat{M}$, its corresponding signless Laplacian $Q_{\hat{M}}$, and the set of higher order adjacency matrices $M_{\ell}$s. We find that, in relation to graphs with at most 10 vertices, $Q_{\hat{M}}$ leads to better results than the signless Laplacian $Q$; besides, when combined with $\hat{M}$, it even surpasses the Godsil and McKay switching method.
Article Number