Descriptive complexity of controllable graphs

09/09/2023
by   Aida Abiad, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset