7
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Descriptive complexity of graph spectra

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 \(C^3\) are co-spectral, and this is not the case with \(C^2\), 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.

          Related collections

          Author and article information

          Journal
          2016-03-22
          2016-09-14
          Article
          10.1007/978-3-662-52921-8_12
          1603.07030
          2e3698a6-4a28-4da6-a2e8-819ea627468a

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Logic, Language, Information, and Computation: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016
          17 pages
          cs.LO

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article