Graph cospectrality using neighborhood matrices

MaRDI QIDQ456353zbMATH OpenFDO

Authors Aline Duarte Bessa, Ivan Carmo Rocha-Neto, Suani Tavares Rubim De Pinho, Roberto Fernandes Silva Andrade, Thierry Correa Petit Lobao

Publication date 24 October 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p23

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cospectralityneighborhood

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

Summary: 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.

Recommendations

• A spectral assignment approach for the graph isomorphism problem
• Enumeration of cospectral graphs.
• Some further development on the eigensystem approach for graph isomorphism detection
• SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISM
• A study of eigenspaces of graphs

Cited in

(3)

• Some further development on the eigensystem approach for graph isomorphism detection
• scientific article; zbMATH DE number 6704556 (Why is no real title available?)
• Study of graph isomorphism using Jordan forms of adjacency matrices

This page was built for publication: Graph cospectrality using neighborhood matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456353)