Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Minimal Laplacian controllability problems of threshold graphs

© The Institution of Engineering and Technology
Received 09/08/2018, Accepted 12/04/2019, Revised 10/01/2019, Published 16/04/2019

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.

Inspec keywords: Laplace equations; network topology; eigenvalues and eigenfunctions; matrix algebra; controllability; graph theory

Other keywords: Laplacian dynamics; binary control matrix; Laplacian eigenvalues; maximum multiplicity; network topology; Laplacian matrix; connected threshold graph Laplacian controllable; minimum number; sufficient condition; minimal Laplacian controllability problems; orthogonal Laplacian eigenvectors; necessary condition

Subjects: Algebra; Combinatorial mathematics; Differential equations (numerical analysis)

References

    1. 1)
      • 17. Olshevsky, A.: ‘Minimal controllability problems’, IEEE Trans. Control Netw. Syst., 2014, 1, pp. 249–258.
    2. 2)
      • 2. Knorn, S., Chen, Z., Middleton, R.H.: ‘Overview: collective control of multiagent systems’, IEEE Trans. Control Netw. Syst., 2016, 3, pp. 334–347.
    3. 3)
      • 24. Mahadev, N.V.R., Peled, U.N.: ‘Threshold graphs and related topics’. Vol. 56 of Annals of discrete mathematics' (North-Holland Publishing Co., Amsterdam, 1995).
    4. 4)
      • 10. Cai, N., He, M., Wu, Q., et al: ‘On almost controllability of dynamical complex networks with noises’, 2017, arXiv..
    5. 5)
      • 13. Cardoso, D.M., Delorme, C., Rama, P.: ‘Laplacian eigenvectors and eigenvalues and almost equitable partitions’, European J Combin, 2007, 28, pp. 665–673.
    6. 6)
      • 8. Mesbahi, M., Egerstedt, M.: ‘Graph theoretic methods in multiagent networks’ (Princeton University Press, Princeton, NJ, 2010).
    7. 7)
      • 32. Godsil, C., Royle, G.: ‘Algebraic graph theory’ (Springer-Verlag, New York, 2001).
    8. 8)
      • 38. Mousavi, S.S., Haeri, M., Mesbahi, M.: ‘Controllability analysis of threshold graphs and cographs’, 2018, arXiv.
    9. 9)
      • 15. Zhang, S., Cao, M., Camlibel, M.K.: ‘Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents’, IEEE Trans. Autom. Control, 2014, 59, pp. 745–750.
    10. 10)
      • 3. Zhao, Y., Liu, Y., Wen, G., et al: ‘Distributed optimization for linear multiagent systems: edge- and node-based adaptive designs’, IEEE Trans. Autom. Control, 2017, 62, pp. 3602–3609.
    11. 11)
      • 6. Almeida, J.A., Silvestre, C., Pascoal, A.: ‘Synchronization of multiagent systems using event-triggered and self-triggered broadcasts’, IEEE Trans. Autom. Control, 2017, 62, pp. 4741–4746.
    12. 12)
      • 36. Aguilar, C.O., Gharesifard, B.: ‘Graph controllability classes for the Laplacian leader-follower dynamics’, IEEE Trans. Autom. Control, 2015, 60, pp. 1611–1623.
    13. 13)
      • 19. Parlangeli, G., Notarstefano, G.: ‘On the reachability and observability of path and cycle graphs’, IEEE Trans. Autom. Control, 2012, 57, pp. 743–748.
    14. 14)
      • 31. Banerjee, A., Mehatari, R.: ‘On the normalized spectrum of threshold graphs’, Linear Algebra Appl., 2017, 530, pp. 288–304.
    15. 15)
      • 27. Hsu, S.P.: ‘Controllability of the multiagent system modeled by the threshold graph with one repeated degree’, Syst. Control Lett., 2016, 97, pp. 149–156.
    16. 16)
      • 39. Sun, C., Hu, G., Xie, L.: ‘Controllability of multiagent networks with antagonistic interactions’, IEEE Trans. Autom. Control, 2017, 62, pp. 5457–5462.
    17. 17)
      • 33. Biggs, N.: ‘Algebraic graph theory’, (Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993, 2nd edn.).
    18. 18)
      • 23. Zhang, S., Camlibel, M.K., Cao, M.: ‘Controllability of diffusively-coupled multi-agent systems with general and distance regular coupling topologies’. 2011 50th IEEE Conf. on Decision and Control and European Control Conf. (CDC-ECC), Orlando, USA, 2011, pp. 759–764.
    19. 19)
      • 7. Wang, Q., Sun, C., Xin, X.: ‘Robust consensus tracking of linear multiagent systems with input saturation and input-additive uncertainties’, Int. J. Robust Nonlinear Control, 2017, 27, pp. 2393–2409.
    20. 20)
      • 11. Liu, Y.Y., Slotine, J.J., Barabási, A.L.: ‘Controllability of complex networks’, Nature, 2011, 473, pp. 167–173.
    21. 21)
      • 20. Hsu, S.P.: ‘A necessary and sufficient condition for the controllability of single-leader multi-chain systems’, Int. J. Robust Nonlinear Control, 2017, 27, pp. 156–168.
    22. 22)
      • 12. Rahmani, A., Ji, M., Mesbahi, M., et al: ‘Controllability of multi-agent systems from a graph-theoretic perspective’, SIAM J. Control Optim., 2009, 48, pp. 162–186.
    23. 23)
      • 9. Chapman, A., Mesbahi, M.: ‘On strong structural controllability of networked systems: a constrained matching approach’. 2013 American Control Conf., Washinton DC, USA, 2013, pp. 6126–6131.
    24. 24)
      • 5. Valcher, M.E., Zorzan, I.: ‘On the consensus of homogeneous multiagent systems with positivity constraints’, IEEE Trans. Autom. Control, 2017, 62, pp. 5096–5110.
    25. 25)
      • 26. Aguilar, C.O., Gharesifard, B.: ‘Laplacian controllability classes for threshold graphs’, Linear Algebra Appl., 2015, 471, pp. 575–586.
    26. 26)
      • 16. Commault, C., Dion, J.M.: ‘The single-input minimal controllability problem for structured systems’, Syst. Control Lett., 2015, 80, pp. 50–55.
    27. 27)
      • 14. Cao, M., Zhang, S., Camlibel, M.K.: ‘A class of uncontrollable diffusively coupled multiagent systems with multichain topologies’, IEEE Trans. Autom. Control, 2013, 58, pp. 465–469.
    28. 28)
      • 30. Molitierno, J.: ‘Applications of combinatorial matrix theory to Laplacian matrices of graphs’ (CRC Press, Boca Raton, FL, 2012).
    29. 29)
      • 29. Hsu, S.P.: ‘Constructing a controllable graph under edge constraints’, Syst. Control Lett, 2017, 107, pp. 110–116.
    30. 30)
      • 21. Notarstefano, G., Parlangeli, G.: ‘Controllability and observability of grid graphs via reduction and symmetries’, IEEE Trans. Autom. Control, 2013, 58, pp. 1719–1731.
    31. 31)
      • 1. Lewis, F.L., Zhang, H., Hengster-Movric, K., et al: ‘Cooperative control of multi-agent systems’ (Springer, Dordrecht, 2014).
    32. 32)
      • 28. Hsu, S.P., Yang, P.Y.: ‘Laplacian controllable graphs based on connecting two antiregular graphs’, IET Control Theory Appl., 2018, 12, pp. 2213–2220.
    33. 33)
      • 25. Merris, R.: ‘Degree maximal graphs are Laplacian integral’, Linear Algebra Appl., 1994, 199, pp. 381–389.
    34. 34)
      • 35. Merris, R.: ‘Laplacian graph eigenvectors’, Linear Algebra Appl., 1998, 278, pp. 221–236.
    35. 35)
      • 22. Nabi-Abdolyousefi, M., Mesbahi, M.: ‘On the controllability properties of circulant networks’, IEEE Trans. Autom. Control, 2013, 58, pp. 3179–3184.
    36. 36)
      • 37. Chen, C.: ‘Linear system theory and design’ (Oxford University Press, New York, 1999, 3rd edn.).
    37. 37)
      • 18. Pequito, S., Ramos, G., Kar, S., et al: ‘The robust minimal controllability problem’, Automatica, 2017, 82, pp. 261–268.
    38. 38)
      • 4. Alvergue, L.D., Pandey, A., Gu, G., et al: ‘Consensus control for heterogeneous multiagent systems’, SIAM J. Control Optim., 2016, 54, pp. 1719–1738.
    39. 39)
      • 34. Bapat, R.B.: ‘On the adjacency matrix of a threshold graph’, Linear Algebra Appl., 2013, 439, pp. 3008–3015.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta.2018.5875
Loading

Related content

content/journals/10.1049/iet-cta.2018.5875
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address