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


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.


graph theory; cospectrality; neighborhood

Full Text: PDF