Descriptive complexity of controllable graphs

Abstract

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,\dots ,A^{n-1}1$ spans the whole space ${\mathbb{R}}^n$. 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.

14 pages