Controllability Analysis of Threshold Graphs and Cographs

In this paper, we investigate the controllability of a linear time-invariant network following a Laplacian dynamics defined on a threshold graph. In this direction, an algorithm for deriving the modal matrix associated with the Laplacian matrix for this class of graphs is presented. Then, based on the Popov-Belevitch-Hautus criteria, a procedure for the selection of control nodes is proposed. The procedure involves partitioning the nodes of the graph into cells with the same degree; one node from each cell is then selected. We show that the remaining nodes can be chosen as the control nodes rendering the network controllable. Finally, we consider a wider class of graphs, namely cographs, and examine their controllability properties.