Controllable Subsets in Graphs.

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 A z 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. [ABSTRACT FROM AUTHOR]