Controllable multi-agent systems modeled by graphs with exactly one repeated degree

Abstract

We consider the controllability of multi-agent dynamical systems modeled by a particular class of bipartite graphs, called chain graphs. Our main focus is related to chain graphs with exactly one repeated degree. We determine all chain graphs with this structural property and derive some properties of their Laplacian eigenvalues and associated eigenvectors. On the basis of the obtained theoretical results, we compute the minimum number of leading agents that make the system in question controllable and locate the leaders in the corresponding graph. Additionaly, we prove that a chain graph with exactly one repeated degree, that is not a star or a regular complete bipartite graph, has the second smallest Laplacian eigenvalue (also known as the algebraic connectivity) in and we show that the second smallest eigenvalue increases when the number of vertices increases. This result is of a particular interest in control theory, since families of controllable graphs whose algebraic connectivity is bounded from below model the systems with a small risk of power or communication failures.