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, …, A^n-11 spans the whole space ℝ^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.
READ FULL TEXT