UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Descriptive Complexity of Graph Spectra

Dawar, A; Severini, S; Zapata, O; (2016) Descriptive Complexity of Graph Spectra. In: Vaananen, J and Hirvonen, A and DeQueiroz, R, (eds.) Logic, Language, Information, and Computation. (pp. pp. 183-199). Springer Green open access

[img]
Preview
Text
1603.07030v5.pdf - Accepted version

Download (221kB) | Preview

Abstract

Two graphs are co-spectral 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 co-spectral 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 C3C3 are co-spectral, and this is not the case with C2C2 , 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.

Type: Proceedings paper
Title: Descriptive Complexity of Graph Spectra
Event: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16–19th, 2016
Location: Benemerita Univ Autonoma Puebla, Dept Comp Sci, Puebla, MEXICO
ISBN-13: 978-3-662-52920-1
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-662-52921-8_12
Publisher version: http://dx.doi.org/10.1007/978-3-662-52921-8_12
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Science & Technology, Technology, Physical Sciences, Computer Science, Theory & Methods, Mathematics, Applied, Computer Science, Mathematics, Descriptive complexity, Algebraic graph theory, Isomorphism approximations, FINITE-MODELS, PALEY GRAPHS, ISOMORPHISM
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1526418
Downloads since deposit
46Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item