Controllable Subsets in Graphs

Abstract

Let $X$ be a graph on $v$ vertices with adjacency matrix $A$, and let 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,\dots ,v-1$ span ${\mathbb{R}}^v$. 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.

14 pages