Chain graphs with simple Laplacian eigenvalues and their Laplacian dynamics

Abstract

We consider a special class of bipartite graphs, called chain graphs, defined as { C3, C5, 2 K2} -free graphs, that have no repeated Laplacian eigenvalues. Our results include structure theorems, degree constraints and examinations of the corresponding eigenspaces. For example, it occurs that such chain graphs do not contain a triplet of vertices with the same neighbourhood, while those with duplicated vertices (pairs with the same neighbourhood) have additional structural restrictions. As an application, we consider the controllability of multi-agent dynamical systems modelled by graphs under consideration with respect to Laplacian dynamics. We construct particular controllable chain graphs and, in general, provide the minimum number of leading agents as well as their locations in the corresponding graph.