Laplacian Controllability for Graphs Obtained by Some Standard Products
- PDF / 285,288 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 191 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Laplacian Controllability for Graphs Obtained by Some Standard Products Milica And¯elic´1
•
Maurizio Brunetti2 • Zoran Stanic´3
Received: 9 September 2019 / Revised: 9 September 2019 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let LG be the Laplacian matrix of a graph G with n vertices, and let b be a binary vector of length n. The pair ðLG ; bÞ is said to be controllable (and we also say that G is Laplacian controllable for b) if LG has no eigenvector orthogonal to b. In this paper we study the Laplacian controllability of joins, Cartesian products, tensor products and strong products of two graphs. Besides some theoretical results, we give an iterative construction of infinite families of controllable pairs ðLG ; bÞ. Keywords Laplacian eigenvalues Controllability Join Cartesian product Tensor product Strong product
Mathematics Subject Classification 05C50 93B05 93C05
1 Introduction We give a very brief introduction, and then go straight to the results. For more details on control systems and their applications, we refer to Ref. [7]. The following equation is a standard model for the single-input linear control systems: & Zoran Stanic´ [email protected] Milica And¯elic´ [email protected] Maurizio Brunetti [email protected] 1
Department of Mathematics, Kuwait University, 13060 Safat, Kuwait
2
Department of Mathematics, University of Naples ‘Federico II’, P. le Tecchio 80, 80125 Naples, Italy
3
Faculty of Mathematics, University of Belgrade, Studentski trg 16, Belgrade 11 000, Serbia
123
Graphs and Combinatorics
dx ¼ Mx þ bu: dt
ð1Þ
The scalar u ¼ uðtÞ is called the control input, while M is an n n real matrix and x; b 2 Rn . The system (1) is called controllable if for any vector x and time t , there always exists a control function uðtÞ; 0\t\t , such that the solution of (1) gives xðt Þ ¼ x irrespective of xð0Þ. In general, any special structure or property of the matrix M or the vector b is not prerequisited. However, case in which M is the Laplacian matrix LG of a graph G and b is a binary vector has received a great deal of attention (see [1, 2, 9]). In this case, the system (1) is controllable if and only if LG has no eigenvector orthogonal to b. In fact, this claim holds for a wider class of matrices [2, 9]. It is also known that if LG has a non-simple eigenvalue, then LG automatically has an associated eigenvector orthogonal to a given vector b [9]. Thus, a necessary condition for the controllability of (1) is that all eigenvalues of LG are simple. We say that the pair ðLG ; bÞ is controllable and also that G is Laplacian controllable for b if the corresponding system is controllable. If LG is not controllable for every binary vector b, then we simply say that G is Laplacian uncontrollable. To simplify terminology, we abbreviate the spectrum, the eigenvalues and the eigenvectors of LG as the spectrum, the eigenvalues and the eigenvectors of G. We use 0 and j to denote the all-0 and the all-1 v
Data Loading...
