Graph isomorphism and multivariate graph spectrum

Wei Wang; Da Zhao

doi:10.1016/j.aam.2025.102994

paper

Graph isomorphism and multivariate graph spectrum

arXiv:2412.20016 · doi:10.1016/j.aam.2025.102994

Abstract

We provide a criterion to distinguish two graphs which are indistinguishable by $2$ -dimensional Weisfeiler-Lehman algorithm for almost all graphs. Haemers conjectured that almost all graphs are identified by their spectrum. Our approach suggests that almost all graphs are identified by their generalized block Laplacian spectrum.

20 pages, 1 figure