Show simple item record

dc.contributor.authorDawar, Anujen
dc.contributor.authorSeverini, Simoneen
dc.contributor.authorZapata, Octavioen
dc.date.accessioned2020-01-07T00:30:40Z
dc.date.available2020-01-07T00:30:40Z
dc.date.issued2019-09en
dc.identifier.issn0168-0072
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/300515
dc.description.abstractTwo 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.
dc.description.sponsorshipOZ was supported by CONACyT-Mexico Grant 384665, SS was supported by EPSRC and The Royal Society.
dc.publisherElsevier
dc.rightsAll rights reserved
dc.rights.uri
dc.titleDescriptive complexity of graph spectra.en
dc.typeArticle
prism.endingPage1007
prism.number9en
prism.publicationDate2019en
prism.publicationNameAnnals of Pure and Applied Logicen
prism.startingPage993
prism.volume170en
dc.identifier.doi10.17863/CAM.47589
rioxxterms.versionofrecord10.1016/j.apal.2019.04.005en
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2019-09en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
rioxxterms.typeJournal Article/Reviewen
cam.issuedOnline2019-04-10en
cam.orpheus.successThu Jan 30 10:34:30 GMT 2020 - Embargo updated*
rioxxterms.freetoread.startdate2020-04-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record