Open AccessMinimal Laplacian controllability problems of threshold graphs
Author(s) -
Hsu ShunPin
Publication year - 2019
Publication title -
iet control theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.059
H-Index - 108
eISSN - 1751-8652
pISSN - 1751-8644
DOI - 10.1049/iet-cta.2018.5875
Subject(s) - laplacian matrix , algebraic connectivity , mathematics , controllability , laplace operator , eigenvalues and eigenvectors , vertex (graph theory) , discrete mathematics , combinatorics , topology (electrical circuits) , resistance distance , adjacency matrix , connectivity , graph , graph power , line graph , mathematical analysis , physics , quantum mechanics
This study is concerned with the minimal controllability problem of a connected threshold graph following the Laplacian dynamics. The goal is to find the minimum number of controllers and a small set of vertices for the controllers to connect to render the graph Laplacian controllable. A simple algorithm is provided to generate a spanning set of orthogonal Laplacian eigenvectors of the graph from a straightforward computation on its Laplacian matrix. A necessary and sufficient condition for the graph to be Laplacian controllable is then proposed. The condition suggests that the minimum number of controllers to make a connected threshold graph Laplacian controllable is the maximum multiplicity of Laplacian eigenvalues of the graph, and this minimum can be achieved using a binary control matrix. If a controller can be connected to one vertex only, the minimum number is the difference between the number of vertices in the graph and the number of vertices with different degrees. The condition also implies that the controllers ensuring the Laplacian controllability should be connected to the vertices with repeating degrees to break the symmetry of the network topology. Several examples are provided to illustrate the authors' results.