Controllable Subsets in Graphs

Let X be a graph on nu 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(r)z for r = 1, . . . , nu - 1 span 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.