Graph isomorphism and multivariate graph spectrum

DOI10.1016/J.AAM.2025.102994MaRDI QIDQ6880982zbMATH OpenFDO

Authors Wei Wang, Da Zhao

Publication date 18 December 2025

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.AAM.2025.102994

zbMATH Keywords

graph identificationgraph isomorphismgraph spectrumWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

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

Cites work

• A note on compact graphs
• A note on cospectral graphs
• An optimal lower bound on the number of variables for graph identification
• Does co-NP have short interactive proofs ?
• Generalized spectral characterizations of regular graphs based on graph-vectors
• Graph isomorphism is in the low hierarchy
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• Isomorphism testing for embeddable graphs through definability
• On the probability that k positive integers are relatively prime
• Operations with structures
• Random Graph Isomorphism
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• The iteration number of the Weisfeiler-Leman algorithm

Cited in

(2)

• Generalized block diagonal Laplacian spectrum of graphs
• On a generalization of the Johnson-Newman theorem to multiple rank-one perturbations

This page was built for publication: Graph isomorphism and multivariate graph spectrum

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