Descriptive complexity of controllable graphs

Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,..., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical prob...

Full description

Saved in:
Bibliographic Details
Main Authors: Abiad, Aida, Dawar, Anuj, Zapata, Octavio
Format: Conference Proceeding
Language:English
Subjects:
counting logics
descriptive complexity
finite model theory
isomorphism problems
spectral graph theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,..., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.
ISSN:1877-0509
1877-0509
DOI:10.1016/j.procs.2023.08.209