Descriptive complexity of graph spectra.
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
Two graphs are cospectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are cospectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic are cospectral, and this is not the case with , nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems.
Description
Keywords
Journal Title
Annals of Pure and Applied Logic
Conference Name
Journal ISSN
0168-0072
Volume Title
170
Publisher
Elsevier
Publisher DOI
Rights
All rights reserved
Sponsorship
OZ was supported by CONACyT-Mexico Grant 384665, SS was supported by EPSRC and The Royal Society.