Minimal Laplacian controllability problems of threshold graphs

被引:8
作者
Hsu, Shun-Pin [1 ]
机构
[1] Natl Chung Hsing Univ, Dept Elect Engn, Taichung, Taiwan
关键词
graph theory; Laplace equations; eigenvalues and eigenfunctions; matrix algebra; controllability; network topology; sufficient condition; minimum number; connected threshold graph Laplacian controllable; Laplacian eigenvalues; binary control matrix; minimal Laplacian controllability problems; Laplacian dynamics; orthogonal Laplacian eigenvectors; Laplacian matrix; necessary condition; maximum multiplicity; COUPLED MULTIAGENT SYSTEMS; OBSERVABILITY; NETWORKS;
D O I
10.1049/iet-cta.2018.5875
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:1639 / 1645
页数:7
相关论文
共 39 条
  • [1] Graph Controllability Classes for the Laplacian Leader-Follower Dynamics
    Aguilar, Cesar O.
    Gharesifard, Bahman
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2015, 60 (06) : 1611 - 1623
  • [2] Laplacian controllability classes for threshold graphs
    Aguilar, Cesar O.
    Gharesifard, Bahman
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 471 : 575 - 586
  • [3] Synchronization of Multiagent Systems Using Event-Triggered and Self-Triggered Broadcasts
    Almeida, Joao
    Silvestre, Carlos
    Pascoal, Antonio
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2017, 62 (09) : 4741 - 4746
  • [4] CONSENSUS CONTROL FOR HETEROGENEOUS MULTIAGENT SYSTEMS
    Alvergue, Luis D.
    Pandey, Abhishek
    Gu, Guoxiang
    Chen, Xiang
    [J]. SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2016, 54 (03) : 1719 - 1738
  • [5] [Anonymous], 1993, ALGEBRAIC GRAPH THEO
  • [6] On the normalized spectrum of threshold graphs
    Banerjee, Anirban
    Mehatari, Ranjit
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 530 : 288 - 304
  • [7] On the adjacency matrix of a threshold graph
    Bapat, R. B.
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (10) : 3008 - 3015
  • [8] Cai N., 2017, ALMOST CONTROLLABILI
  • [9] A Class of Uncontrollable Diffusively Coupled Multiagent Systems with Multichain Topologies
    Cao, Ming
    Zhang, Shuo
    Camlibel, M. Kanat
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2013, 58 (02) : 465 - 469
  • [10] Laplacian eigenvectors and eigenvalues and almost equitable partitions
    Cardoso, Domingos M.
    Delorme, Charles
    Rama, Paula
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (03) : 665 - 673