Controllable Subsets in Graphs

By Chris D. Godsil. 2010

82 citations recorded by the source corpus.

Let X be a graph on ν vertices with adjacency matrix A, and let S be a subset of its vertices with characteristic vector z. We say that the pair (X, S) is controllable if the vectors Arz for r =  1, . . . , ν − 1 span $${\mathbb{R}^{\nu}}$$ . Our concern is chiefly with the cases where S = V(X), or S is a single vertex. In this paper we develop the basic theory of controllable pairs. We will see that if (X, S) is controllable then the only automorphism of X that fixes S as a set is the identity. If (X, S) is controllable for some subset S then the eigenvalues of A are all simple.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/3c176611c83b4a8b30f807871d338fb82bb21baf