×

Laplacian controllability classes for threshold graphs. (English) Zbl 1307.05135

Summary: Let \(\mathcal{G}\) be a graph on \(n\) vertices with Laplacian matrix \(\mathbf{L}\) and let \(\mathbf{b}\) be a binary vector of length \(n\). The pair \((\mathbf{L}, \mathbf{b})\) is controllable if the smallest \(\mathbf{L}\)-invariant subspace containing \(\mathbf{b}\) is of dimension \(n\). The graph \(\mathcal{G}\) is called essentially controllable if \((\mathbf{L}, \mathbf{b})\) is controllable for every \(\mathbf{b} \notin \ker (\mathbf{L})\), completely uncontrollable if \((\mathbf{L}, \mathbf{b})\) is uncontrollable for every \(\mathbf{b}\), and conditionally controllable if it is neither essentially controllable nor completely uncontrollable. In this paper, we completely characterize the graph controllability classes for threshold graphs. We first observe that the class of threshold graphs contains no essentially controllable graph. We prove that a threshold graph is completely uncontrollable if and only if its Laplacian matrix has a repeated eigenvalue. In the process, we fully characterize the set of conditionally controllable threshold graphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C90 Applications of graph theory
93B05 Controllability
93C05 Linear systems in control theory
Full Text: DOI

References:

[1] Aguilar, C.; Gharesifard, B., Graph controllability classes for the Laplacian leader-follower dynamics, IEEE Trans. Automat. Control (2015), in press · Zbl 1360.93085
[2] Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, (Annals of Discrete Mathematics, vol. 1 (1977)), 145-162 · Zbl 0384.90091
[3] Cvetković, D.; Rowlinsonand, P.; Stanic, Z.; Yoon, M., Controllable graphs with least eigenvalue at least −2, Appl. Anal. Discrete Math., 5, 2, 165-175 (2011) · Zbl 1265.05359
[4] Farrugia, A.; Sciriha, I., Controllability of undirected graphs, Linear Algebra Appl., 454, 138-157 (2014) · Zbl 1288.05155
[5] Godsil, C., Controllable subsets in graphs, Ann. Comb., 16, 733-744 (2012) · Zbl 1256.05139
[6] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2004), Elsevier · Zbl 1050.05002
[7] Hagberg, A.; Stewart, P.; Shult, D., Designing threshold networks with given structural and dynamical properties, Phys. Rev. E, 74, 056116 (2006)
[8] Hammer, P. L.; Kelmans, A. K., Laplacian spectra and spanning trees of threshold graphs, Discrete Appl. Math., 65, 255-273 (1996) · Zbl 0860.05055
[9] Henderson, P.; Zalcstein, Y., A graph-theoretic characterization of the PV class of synchronizing primitives, SIAM J. Comput., 6, 88-108 (1977) · Zbl 0349.68022
[10] Ji, Z.; Lin, H.; Yu, H., Leaders in multi-agent controllability under consensus algorithm and tree topology, Systems Control Lett., 61, 918-925 (2012) · Zbl 1270.93017
[11] Ji, Z.; Wang, Z.; Lin, H.; Wang, Z., Interconnection topologies for multi-agent coordination under leader-follower framework, Automatica, 45, 2857-2863 (2009) · Zbl 1192.93013
[12] Kalman, R.; Ho, Y.; Narendra, K., Controllability of Linear Dynamical Systems, Contributions to the Theory of Differential Equations, vol. 1 (1963), Interscience · Zbl 0151.13303
[13] Mahadev, N.; Peled, U., Threshold Graphs and Related Topics, vol. 56 (1995), Elsevier · Zbl 0852.05001
[14] Merris, R., Laplacian graph eigenvectors, Linear Algebra Appl., 278, 221-236 (1998) · Zbl 0932.05057
[15] Notarstefano, G.; Parlangeli, G., Controllability and observability of grid graphs via reduction of symmetries, IEEE Trans. Automat. Control, 58, 7, 1719-1731 (2013) · Zbl 1369.93087
[16] Olfati-Saber, R.; Fax, J.; Murray, R., Consensus and cooperation in networked multi-agent systems, (Proc. IEEE, vol. 95 (2007)), 215-233 · Zbl 1376.68138
[17] Parlangeli, G.; Notarstefano, G., On the reachability and observability of path and cycle graphs, IEEE Trans. Automat. Control, 57, 3, 743-748 (2012) · Zbl 1369.93382
[18] Rahmani, A.; Ji, M.; Mesbahi, M.; Egerstedt, M., Controllability of multi-agent systems from a graph-theoretic perspective, SIAM J. Control Optim., 48, 1, 162-186 (2009) · Zbl 1182.93025
[19] Saha, S.; Ganguly, N.; Mukherjee, A.; Krueger, T., Intergroup networks as random threshold graphs, Phys. Rev. E, 89, 042812 (Apr. 2014)
[20] Tanner, H., On the controllability of nearest neighbor interconnections, (IEEE Conf. on Decision and Control (2004)), 2467-2472
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.