Laplacian Controllability for Graphs with Integral Laplacian Spectrum

Abstract

If G is a graph with n vertices, LG is its Laplacian matrix, and b is a binary vector of length n, then the pair (LG, b) is said to be controllable, and we also say that G is Laplacian controllable for b, if b is non-orthogonal to any of the eigenvectors of LG. It is known that if G is Laplacian controllable, then it has no repeated Laplacian eigenvalues. If G has no repeated Laplacian eigenvalues and each of them is an integer, then G is decomposable into a (dominate) induced subgraph, say H, and another induced subgraph with at most three vertices. We express the Laplacian controllability of G in terms of that of H. In this way, we address the question on the Laplacian controllability of cographs and, in particular, threshold graphs.