Descriptive complexity of graph spectra
DOI10.1016/j.apal.2019.04.005zbMath1430.68119arXiv1603.07030MaRDI QIDQ2273011
Simone Severini, Anuj Dawar, Octavio Zapata
Publication date: 18 September 2019
Published in: Annals of Pure and Applied Logic, Logic, Language, Information, and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.07030
strongly regular graphs; algebraic graph theory; spectral graph theory; finite model theory; descriptive complexity; isomorphism problems; isomorphism approximations; counting logics
05E30: Association schemes, strongly regular graphs
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
03C80: Logic with extra quantifiers and operators
03C13: Model theory of finite structures
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
68Q19: Descriptive complexity and finite models
