A graph-theoretic classification for the controllability of the Laplacian leader-follower dynamics

In this paper, we revisit the controllability problem for the Laplacian based leader-follower dynamics with the aim of addressing some fundamental gaps within the existing literature. We introduce a notion of graph controllability classes for Laplacian based leader-follower control systems, namely, the classes of essentially controllable, completely uncontrollable, and conditionally controllable graphs. In addition to the topology of the underlying graph, our controllability classes rely on the richness of the set of control vectors. The particular focus in this paper is on the case where this set is chosen as the set of binary vectors, which captures the case when the control signal is broadcasted by the leader nodes. We first prove that the class of essentially controllable graphs is a strict subset of the class of asymmetric graphs. We provide a non-trivial class of completely uncontrollable asymmetric graphs, namely the class of large block graphs of Steiner triple systems. Several constructive examples demonstrate our results.