Id: arxiv/2602.00936 Url: https://arxiv.org/abs/2602.00936 Tags: math.CO Score: 0 Title: Natural graph spectra Domain: math.CO Source: arxiv Authors: Ziqing Xiang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-01-31 Page: https://delphi.science/r/arxiv/2602.00936 In 2003, van Dam and Haemers posed a fundamental question in spectral graph theory: does there exist a ``sensible'' matrix whose spectrum determines a random graph up to isomorphism? This paper introduces the class of {\em natural graph matrices}, which are matrices defined by applying a fixed sequence of elementary operations to the adjacency matrix. This class includes many standard matrices such as the adjacency matrix, the Seidel matrix, the Laplacian matrix, and the distance matrix. We give an affirmative answer to the question of van Dam and Haemers by proving the existence of a…