Controllable multi-agent systems modeled by graphs with exactly one repeated degree

1.   Introduction

Many modern engineering problems and their solutions are related to the controllability of leader-follower, multi-agent, dynamical systems such as power monitoring systems, constructing autopilots, ventilation and air-conditioning systems, constructing and monitoring drone swarm systems, distributed energy management and energy systems and wireless, sensor networks (see ^[1,2,3,4] as well as ^[5,6,7]). Typically, graphs are used to model such systems. Vertices represent the agents (partitioned into leaders and followers), while the interaction between the agents is represented by the edges. Structural and some other properties of the underlying graph are crucial to construct systems that satisfy some particular requirements.

A multi-agent dynamical system is said to be controllable if it can move from any initial state to any other state in a finite time. A study on the controllability of general multi-agent networks was conducted in ^[8,9]. Since then, a theoretical framework for the controllability of systems has developed significantly. Simultaneously, a study on the controllability of particular networks has received a noteworthy attention. One can reference the following for antagonistic ^[10,11], directed ^[12,13], or signed networks ^[14,15,16].

In this paper, our focus is on the classical Kalman's rank controllability condition applied to the Laplacian matrix with off-diagonal entries belonging to $\{0, -1\}$. Recently, the study was centered around a structural controllability (i.e., around weighted matrices). A system is structurally controllable if and only if there is at least one choice of edge weights such that it is controllable. This concept was introduced in ^[17], along with necessary and sufficient conditions for complex networks to have this property. According to the same reference (see also ^[18,19,20]), under this setup, it turns out that the structural controllability purely depends on the topology of the communication scheme, and the multi-agent system is structurally controllable if and only if the graph is connected. An additional study extends to strong structural controllability that required the system to be controllable for any choice of weights ^[21,22,23]. A slightly weaker notion than controllability is stabilizability, where a system is said to be stabilizable when all the uncontrollable state variables can be made to have stable dynamics (see ^[24] and references therein).

We consider the controllability of a multi-agent dynamical systems modeled by a particular class of bipartite graphs called chain graphs. Many real-world networks are bipartite including the following: Community ecology networks, islands biogeography networks, social network forums, networks of scientists and research papers and the human drug-target protein networks ^[25,26]. In particular, chain graphs are met when modelling the systems that contain the so-called nesting property. In an informal sense, nestedness refers to a hierarchical organization where the set of neighbors of a vertex is a subset of the set of neighbors of a vertex of lower degree. This property can be found in a wide branch of systems including ecological interaction networks, trade networks, inter-organizational networks, firm spatial networks, interbank payment networks, or social-media networks (see the survey paper ^[27]), as well as in many biological or medical networks (see the survey paper ^[28]). In this study, we are interested in chain graphs with exactly one repeated vertex degree. By the pigeonhole principle one may observe that every graph distinct from the single vertex contains at least one pair of vertices sharing the same degree. In the light of this, our attention is focused on an extreme case in which two vertices differ in degree, unless they belong to a fixed and comparatively small vertex subset. The significance of such graphs in modelling the real-life systems is recognized in ^[26] where, on the basis of exhaustive empirical experiments, the authors have deduced that as the network's degree distribution became increasingly heterogeneous, the entire system became easier to control. According to the same reference, the follower vertices tend to avoid vertices with high degrees in random networks. In relation to this, we will show that in our model, unless we deal with certain simple cases, vertices with the maximum degree are reserved to leading agents and a single follower, which introduces an example that bypasses the previous rule.

A chain graph is a graph that does not contain neither a pair of non-adjacent edges, nor a triangle, nor a pentagon (that is, a five vertex cycle) as an induced subgraph. Using the standard graph theoretical notation, we can say that a chain graph is a $\{2K_2, C_3, C_5\}$-free graph. It follows from the previous definition that every chain graph is bipartite. The controllability of multi-agent systems modeled by chain graphs that have multiple repeated vertex degrees has been considered in ^[29,30]. If only one vertex degree is repeated, it follows that such a chain graph is either a star, or a regular complete bipartite graph, or it belongs to a particular infinite family. In this way, we provide a new family of graphs that model controllable systems which have only one repeated vertex degree and possess several distinguishable properties related to the connectivity. The existence of such graphs was questioned in ^[31].

The remainder of the paper is organized as follows. In Section 2, we provide some preliminary results, the formulation, and the motivation of the problem. In Section 3, we put our focus on chain graphs with exactly one repeated degree; in particular, we determine all such graphs and report the results which concern the Laplacian eigenvalues and the corresponding eigenvectors. In Section 4, we consider the controllability of systems modeled by a corresponding chain graph. Some concluding remarks are separated in Section 5.

2.   Preliminaries

2.1.   Framework

We assume that $G = (V, E)$ is a simple, undirected graph, without loops or multiple edges. Its order $n$ is the number of vertices. The number of edges is known as the size. As usual, we denote the $(0, 1)$-adjacency matrix of $G$ by $A(G)$, the diagonal matrix of vertex degrees by $D(G)$, and by $L(G) = D(G)-A(G)$ the Laplacian matrix of $G$. The Laplacian eigenvalues of $G$ are the eigenvalues of $L(G)$ and they form the Laplacian spectrum of $G$, which is denoted by $\sigma (G)$. To simplify the language, we occasionally suppress the prefix 'Laplacian' in this terminology. The matrix $L(G)$ is symmetric and a positive semidefinite. Moreover, 0 is always an eigenvalue associated with the all-$1$ eigenvector. Therefore, we may assume that the eigenvalues of $G$ (in fact, the roots of the characteristic polynomial $\phi(L(G), x) = \det(x I-L(G))$) are indexed in a non-increasing order and are given as follows:

The second smallest eigenvalue $\mu_{n-1}(G)$ is called the algebraic connectivity, and it will be denoted by $a(G)$. It is greater than 0 if and only if $G$ is connected [32, Theorem 7.1.2]. The algebraic connectivity is frequently investigated as an eigenvalue that measures the connectivity, the robustness, and the synchronisation of a graph ^[33,34].

Our focus is on a multi-agent system with $n$ linear agents $\{1, 2, \ldots, n\}$ modeled by a graph $G$, in the sense that the agents are interpreted as the vertices, and their connections are interpreted by the edges. Accordingly, the terms 'vertex' and 'agent' are alternatively used throughout the text (i.e., the vertex $v_i$ stands for the state of the agent $i$ in a network), which evolves in line with the following consensus equation:

where $N(i)$ is the set of all neighbors of $i$. The shorthand dynamics can be written as $\dot{\mathbf{v}}(t) = -L(G)\mathbf{v}(t)$, and is known as the Laplacian dynamics. The vector $\mathbf{v}$ is the vector of the agents' states and $L(G)$ is the Laplacian matrix of $G$, as specified.

Following ^[35], ℓ and $\mathbf{f}$ denote the set of leaders and the set of followers (i.e., the set of leading and the following agents, respectively). Accordingly, the Laplacian $L(G)$ can be written in the following block representation form:

where the top-left block corresponds to the followers, the bottom-right block corresponds to the leaders, and the remaining two blocks represent the interactions between them.

The core of our attention are the leader-follower systems:

with followers evolving through the Laplacian-based dynamics

The external control signal ran by the leaders' states is denoted by $\mathbf{u}$. In other words, we suppose that $n$ control input $\mathbf{u}(t) = (u_1(t), u_2(t), \ldots, u_n(t))^\intercal$ is applied to (2.1) via the control input $(0, 1)$-matrix $-l_{f\ell}(G)$. Note that the columns of this matrix are binary control vectors, such that the $j$th entry in $i$th column is $1$ if the $j$th state, variable which directly receives the signals from the $i$th input, and is $0$ otherwise.

A controllable system refers to the system modeled by (2.2) that can be driven from any initial state to any desired terminal state in a finite time. Such systems are found in many areas of science and engineering, see for example ^{[31,36,37,38,39]}. The controllability of multi-agent systems in the majority of cases deal with locations of leaders under which the controllability can be achieved. If the minimum number of leaders needed to make (2.2) controllable is $k$, then we say that (2.2) is $k$-leaders controllable.

The Kalman's rank condition states that the system (2.2) is controllable if the controllability matrix

has the full row rank $n$. We recall an equivalent spectral argument needed for our further analysis. It enables the use of sophisticated spectral graph theory tools to deal with the controllability of multi-agent systems and the determination of the set of leaders.

Lemma 2.1. (^[35]) The system (2.2) is controllable if and only if there is no eigenvector for $L(G)$ taking $0$ on all entries corresponding to leaders, i.e., if and only if $L(G)$ and $\mathcal{L}_f(G)$ do not share any common eigenvalue.

2.2.   Chain graphs

The vertex set of a chain graph $G$ consists of two color classes, partitioned into $h$ non-empty cells $\bigcup_{i = 1}^h U_i$ and $\bigcup_{i = 1}^h V_i$, respectively. All vertices in $U_s$ are joined to all vertices in $\bigcup_{k = 1}^{h+1-s} V_k$, for $1\leq s\leq h$. Therefore, all vertices in $U_i$ (resp. $V_j$) are co-neighbors (i.e., they share the same set of neighbors). If $m_s = |U_s|$ and $n_s = |V_s|$, for $1\leq s\leq h$, then $G$ is denoted by ${{\rm{CG}}}(m_1, m_2, \ldots, m_h; n_1, n_2, \ldots, n_h).$ The parameter $h$ is known as the height of a chain graph, and the structure is sketched in Figure 1. Additionally, chain graphs appear under the name double nested graphs, which emphasizes their double nesting structure ^[40].

The degrees of vertices in $U_i$ are denoted by $d_i$, and we have the following:

Similarly, the vertex degrees in $V_i$ are denoted by $d^*_i$, along with the following:

Any chain graph admits an equitable vertex partition:

which means that any vertex in $U_i$ or $V_j$ has a constant number of neighbors in any of sets $U_k, V_l$, $1\leq k, l\leq h$. The quotient matrix $Q$ of the Laplacian matrix of $G$ corresponding to the equitable partition $\Pi$ is the matrix whose entries are the constant row sums of the corresponding blocks of $L(G)$. It is of the following form:

where

and $D_1 = {{\rm{diag}}}(d_1, d_2, \ldots, d_h), D_2 = {{\rm{diag}}}(d^*_1, d^*_2, \ldots, d^*_h)$. The spectrum is comprised of $d_i$ with the multiplicity $m_i-1$, $d^*_i$ with multiplicity $n_i-1$, $1\leq i\leq h$, and the eigenvalues of $Q$. For more details on the spectrum of chain graphs via equitable partitions, the reader is referred to ^[29].

2.3.   Formulation of the problem and motivation

Our interest on the controllability of chain graphs with one repeated degree stems from the following three prominent facts.

Chain graphs feature as maximizers for the largest Laplacian eigenvalue in the class of connected bipartite graphs of fixed order and size, see ^[40]. In this context, they are recognized as bipartite counterparts to the so-called threshold graphs that maximize the same eigenvalue in the class of all connected graphs with a fixed order and size. Motivated by questions raised by Hsu in ^[31] and the aforementioned relation between chain and threshold graphs, we provide a new family of graphs with only one repeated degree that model controllable systems (2.2).

According to ^[31], families of graphs whose algebraic connectivity is bounded from below by a positive constant are of a particular interest in the control theory, since such graphs model the systems with a high reachability between the agents and a small risk of power or communication failures. By the same source, in the majority of known controllable systems modeled by graphs, the algebraic connectivity decreases when the graph order increases; in these cases, determining a lower bound is a challenging problem. In this context, it is worth mentioning that chain graphs with exactly one repeated degree have a distinguishable property: Their algebraic connectivity increases when the order increases, as proved in Section 3. Accordingly, the lower bound is easily determined, since it is attained for the graph with the smallest order. Moreover, the algebraic connectivity of a chain graph which has exactly one repeated degree, and is not a star nor a regular complete bipartite graph, is not less than $0.8299$ and does not exceed $1$, as shown later.

A chain graph is uniquely determined by the degree sequence, say $\pi$, of one color class ^[41]. The vertex degrees of one color class form Ferrers diagrams, while the vertex degrees of the other color class are obtained from its conjugate. The conjugate of the Ferrers diagram $F(\pi)$ is equal to $F(\pi)^\intercal$, which is the transpose of $F(\pi)$. For instance, if $\pi = (5, 4, 3, 3, 1)$, then $\pi^* = (5, 4, 4, 2, 1)$.

3.   Chain graphs with exactly one repeated degree, their eigenvalues and eigenspaces

3.1.   Structure

In this section, we investigate relationships between the structure and the spectrum of chain graphs with exactly one repeated degree. First, we determine the parameters that define such chain graphs.

We single out one possibility.

Lemma 3.1. The chain graph $CG(m, n)$ has exactly one repeated degree if and only if it is a star or a regular complete bipartite graph.

Proof. The result is a simple structural examination on chain graphs with $h = 1$. □

The next result refers the main case $h\geq 2$ and completes the entire class.

Theorem 3.2. For $h\geq 2$, let $G\cong {{\rm{CG}}}(m_1, m_2, \ldots, m_h; n_1, n_2,$ $\ldots, n_h)$ be a chain graph with exactly one repeated degree. Then $G\cong {{\rm{CG}}}(\underbrace{\kappa, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$, for $\kappa\geq h$.

Proof. We claim that only one of $m_i$'s, $n_i$'s can be greater than $1$. First, if $m_i, m_j\geq 2$, for $1\leq i\neq j\leq h$, then the vertices in $U_i$ share the same degree, and the same holds for the vertices in $U_j$. Moreover, from (2.3), we have that $u\in U_i$ and $v\in U_j$ differ in degree, which contradicts the statement assumption. Therefore, at most one $m_i$ is greater than 1, and the same holds for at most one $n_i$. If $m_i\geq 2$ and $n_j\geq 2$, then we deduce that $u\in U_i$ and $v\in V_j$ must have the same degree, which implies $j = h+1-i$, by (2.3) and (2.4). Considering the vertices of $U_k$ and $V_{h+1-k}$, for $k\neq i$, we conclude that they are equal in degree; on the other hand, those of $U_i$ and $U_k$ differ in degree, which is a contradiction. Therefore, the claim holds true.

Assume, without a loss of generality, that $m_i = \kappa\geq 2$. If $i > 1,$ then the degrees of vertices in $U_1, U_2, \ldots, U_h$ are

whereas the degrees of vertices in $V_1, V_2, \ldots, V_h$ are

It follows that there are at least two repeated degrees $h+1-i$ and $1$. Consequently, we conclude that $i = 1$. Then, among degrees

there is only one repeated if and only if $\kappa\geq h$. This completes the proof. □

3.2.   Eigenvalues

We consider the spectral properties of graphs determined in Theorem 3.2.

Theorem 3.3. Let $G\cong {{\rm{CG}}}(\underbrace{\kappa, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$, for $\kappa\geq h\geq 2$. Then,

where

Proof. Taking into account that $d_i = h+1-i$ ($1\leq i\leq h$) and $d_j^* = \kappa+h-j$ ($1\leq j\leq h$) and employing [41, Theorem 3.5], we obtain that the characteristic polynomial $\phi(L(G), x)$ is given by

for $p_j = (d^*_j-x)(x-d_{h+1-j}).$ Since $x(x-h)^{\kappa-1}$ is a factor of $\phi(L(G), x)$, the remaining eigenvalues are the roots of the following polynomial:

By a direct computation, we obtain the following identities:

● $f(0) = (-1)^{\kappa+h}(2h+\kappa-1)\frac{(\kappa+h-2)!}{h}$;

● $f(1) = (-1)^{\kappa+h+1}(\kappa+h-3)(\kappa+h-3)!$;

● $f(\ell) = (-1)^{\kappa+h+\ell}2\ell(h+1)(\ell-1)!(\kappa+h-2\ell-2)!\frac{(\kappa+h-\ell-1)!}{(\kappa+h-2\ell)!}$, for $2\leq \ell\leq h-1$;

● $f(\kappa) = (-1)^{h+1}\frac{\kappa!}{(\kappa-h+1)(\kappa-h)} (h-1)!;$

● $f(\kappa+\ell) = (-1)^{h-\ell+1}2(\ell+1)\frac{(\kappa+\ell)!}{(\kappa+2\ell-h+1)(\kappa+2\ell-h)}(h-\ell-1)!$, for $1\leq\ell\leq h-1$;

● $f(\kappa+h) = -(\kappa+h-2)\cdot (h-1)! < 0$.

Next, we conclude that $f(0), f(1), \ldots, f(h-1)$ alternate in sign. Consequently, for every $i \in\{1, 2, \ldots, h-1\}$, we have $f(x_i) = 0$, for some $x_i\in(i-1, i)$. A similar argument holds for $f(\kappa), f(\kappa+1), \dots, f(\kappa+h-1)$; therefore, for every $i\in\{\kappa+1, \kappa+2, \ldots, \kappa+h-1\}$ we have $p(x_i) = 0$, for some $x_i\in(i-1, i)$. Additionally, since $f$ is monic and $f(\kappa+h) < 0$, it follows that $f(x_{2h}) = 0$ holds for some $x_{2h} > \kappa+h$, which concludes the proof. □

We record an easy consequence.

Corollary 3.4. Let $G\cong {{\rm{CG}}}(\underbrace{\kappa, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$, for $\kappa\geq h\geq 2$. Then, $G$ has no non-integer Laplacian eigenvalues in $(h-1, \kappa)$.

Theorem 3.3 yields that the algebraic connectivity of a chain graph under consideration does not exceed $1$. In what follows, we derive a lower bound for the same eigenvalue and show that it increases when the order of $G$ increases. First, we state a useful lemma and observe that it remains valid for $h = 1$.

Lemma 3.5. Let $G\cong {{\rm{CG}}}(m_1, m_2, \ldots, m_h; n_1, n_2, \ldots, n_h)$ and $G'\cong {{\rm{CG}}}(m'_1, m'_2, \ldots, m'_h; n'_1, n'_2, \ldots, n'_h)$. If $m_i\geq m'_i$ and $n_i\geq n'_i$ for every $i\in\{1, 2, \ldots, h\}$, then $\mu_i(Q)\geq \mu_i(Q')$, where $Q$ and $Q'$ are the corresponding quotient matrices given in (2.5).

Proof. The desired result follows from a classical result for Hermitian matrices, see [42, Corollary 7.7.4(c)], which states that the corresponding inequalities between the eigenvalues of $Q$ and $Q'$ hold whenever $Q-Q'$ is a positive semidefinite. Indeed, we easily confirm that the diagonal elements of this matrix are dominant which, by [42, p. 392], completes the assertion. □

We proceed with a lower bound for the algebraic connectivity.

Theorem 3.6. Let $G\cong {{\rm{CG}}}(\underbrace{\kappa, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$, for $k\geq h\geq 2$. Then, $a(G)\in [\xi, \, 1)$, where $\xi$ is the algebraic connectivity of ${{\rm{CG}}}(2, 1;1, 1)$, which is approximately equal to $0.829914$.

Proof. Since $h\geq 2$, from Theorem 3.3, we have $a(G) < 1$. By the Interlacing Theorem for the Laplacian spectrum (see [32, Theorem 7.2.5]), we have $a(G)\geq a(G')$, where $G'\cong {{\rm{CG}}}(\kappa, h-1;1, h-1)$. $G'$ is obtained from $G$ by deleting all edges that connect vertices in $U_i$, for $2\leq i\leq h-1$, with all vertices in $V_j$, for $2\leq j\leq h-1$. From Lemma 3.5, we obtain $a(G')\geq a(G'')\geq a(G''')$, where $G''\cong {{\rm{CG}}}(h, h-1;1, h-1)$ and $G'''\cong {{\rm{CG}}}(2, 1;1, 1)$, and the result follows.□

The previous lower bound is sharp at least for ${{\rm{CG}}}(2, 1;1, 1)$. Additionally, for every chain graph $G$ with exactly one repeated degree, $a(G)\in (0.8299, 1]$ holds. The next result is an interesting phenomenon in which the algebraic connectivity increases with the order.

Corollary 3.7. Let $G_1\cong {{\rm{CG}}}(\underbrace{\kappa_1, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$ and $G_2\cong {{\rm{CG}}}(\underbrace{\kappa_2, 1, 1, \ldots, 1}_h; \underbrace{1, 1, \ldots, 1}_h)$, with $\kappa_2\geq \kappa_1\geq h\geq 1$. Then, $a(G_1)\leq a(G_2)$. In addition, $a(CG(\kappa_1, \kappa_1))\leq a(CG(\kappa_2, \kappa_2))$.

Proof. For $h = 1$, $G_1$ and $G_2$ are stars, along with $a(G_1) = a(G_2) = 1$. By the previous theorem, the algebraic connectivity of both graphs is non-integer for $h\geq 2$, which implies that it is not equal to any of the vertex degrees. Therefore, it belongs to the spectrum of the corresponding quotient matrix, and the result follows from Lemma 3.5.

Finally, for $i\in\{1, 2\}$, $CG(\kappa_i, \kappa_i)$ is regular complete bipartite, and its algebraic connectivity is $\kappa_i$ (see [43, p. 17]). This observation concludes the entire proof. □

We continue with an illustration.

Example 3.8 Let $G_1\cong {{\rm{CG}}}(6, 1, 1, 1, 1;1, 1, 1, 1, 1)$ and $G_2 = {{\rm{CG}}}(7, 1, 1, 1, 1;1, 1, 1, 1, 1)$. Then,

Now, one may compare the eigenvalues according to Lemma 3.5, in particular, $0.8299 < 0.96\approx a(G_1) < a(G_2)\approx 0.97 < 1$.

It is noteworthy to add that, in contrast to our situation, if the order of $G$ is increased by augmenting its height $h$ while the number of vertices with a repeated degree remains unchanged, then the algebraic connectivity may decrease.

3.3.   Eigenvectors

The eigenspace of the eigenvalue $h$ (of multiplicity $\kappa-1$) is generated by the following eigenvectors:

In what follows, we observe the structure of eigenvectors of $L(G)$ which correspond to non-integral eigenvalues in the main case (i.e., $h\geq 2$).

Theorem 3.9. For $G\cong {{\rm{CG}}}(\kappa, 1, 1, \ldots, 1; 1, 1, \dots, 1)$ with $\kappa\geq h\geq 2$, let $\mu$ be a non-integral eigenvalue and $\mathbf{x} = (x_1, x_2, \ldots, x_{n})^\intercal$ be an associated eigenvector according to the following vertex ordering: $U_1, U_2, \ldots, U_h, V_1, V_2, \ldots, V_h$. Then, $x_i\neq 0$, for every $1\leq i\leq \kappa$.

Proof. On the contrary, assume that $\mathbf{x}$ is an eigenvector for a non-integral eigenvalue $\mu$ of $L(G)$ such that $x_i = 0$ holds for $1\leq i\leq \kappa$. Let

By the eigenvalue equations for all the entries corresponding to the vertices in $U_1$, we obtain the following:

i.e.,

The eigenvalue equation for the vertex in $V_h$ implies $\mu y_h = d^*_h y_h+0$. Since $\mu\notin\mathbb{Z}$, it follows that $y_h = 0$, and together with (3.1), this gives the following:

Next, for the entry which corresponds to the vertex in $U_2$, we obtain the following:

which is equivalent to $(\mu-d_2) x_{2} = 0$ (i.e., to $x_{2} = 0$).

In a similar way, the eigenvalue equation for the vertex in $V_{h-1}$ gives $y_{h-1} = 0$, and so on until we obtain $x_1 = x_2 = \cdots = x_h = y_1 = y_2 = \cdots = y_h = 0$, that is $\mathbf{x} = \mathbf{0},$ which is impossible. □

4.   Controllability of the corresponding systems

In this section, we show that the systems (2.2) modeled by the chain graphs considered in the previous sections are controllable. Additionally, we compute the minimum number of leading agents and identify their positions in the corresponding graph.

Theorem 4.1. Let $G\cong {{\rm{CG}}}(\kappa, 1, 1, \ldots, 1;1, 1, \ldots, 1)$ with $\kappa\geq h\geq 1$. Unless $\kappa = h = 1$, the system (2.2) modeled by $G$ is controllable with $\kappa-1$ co-neighbor vertices in the role of leaders. For $\kappa = h = 1$, the graph reduces to the complete graph $K_2$, and the system is $1$-leader controllable with any vertex in the role of a leader.

Proof. For $G\cong K_2$, the result follows by a simple algebraic computation. Suppose $G\not\cong K_2$. Since the eigenspace of $h$ is generated by the eigenvectors listed at the beginning of this subsection, in the light of Lemma 2.1, we deduce that every vertex outside $U_1$ does not belong to the minimum set of leading agents. Each of the vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_{\kappa-1}$ has the following form:

for some $\alpha_1, \alpha_2, \ldots, \alpha_{\kappa-1}\in\mathbb{R}$. Therefore, any eigenvector of $L(G)$ for $h$ takes $0$ on all entries which correspond to $V(G)\setminus U_1$. In addition, for any proper subset $S$ of $\{2, 3, \ldots, \kappa\}$, there exists a linear combination of the above eigenvectors taking zero on every vertex, which by the same lemma leads to the conclusion that there is at least one leader outside $S$.

Next, consider the set $\{2, 3, \ldots, \kappa\}$, denoted again by $S$. If $\mathbf{x}$ takes zero on the entire $S$, then $\mathbf{x} = \mathbf{0}$, which is impossible. Moreover, by Theorem 3.3, the remaining eigenvalues are non-integral; then, by Theorem 3.9, their eigenvectors do not take zero on $U_1$, and neither on $S$. Hence, we have proved that no eigenvector for $L(G)$ takes $0$ on all entries which correspond to $S$. By Lemma 2.1, $S$ corresponds to the minimum set of leading agents. □

The previous theorem covers all chain graphs with exactly one repeated degree, except regular complete bipartite graphs of degree at least two. They are treated in the next remark.

Remark 4.2. Following the proof of Theorem 4.1, we deduce that the minimum set of leaders of the system (2.2) modeled by $G\cong CG(\kappa, \kappa)$, $\kappa\geq 2$, consists of $2(\kappa-1)$ agents, such that $\kappa-1$ belong to one color class of $G$ and the remaining $\kappa-1$ are in the other class.

Theorem 4.1 gives infinite families of controllable systems. Indeed, we may fix $h$ and take an arbitrary $\kappa\geq h$ to obtain a $(\kappa-1)$-leaders controllable system, without any additional condition. Here is an illustration.

Example 4.3. For $G\cong {{\rm{CG}}}(7, 1, 1, 1, 1;1, 1, 1, 1, 1)$, the system (2.2) is $6$-leaders controllable. The leaders

are $6$ of the $7$ co-neighbors of degree 5, as illustrated in Figure 2. Together with $u_1$, they belong to the cell $U_1$ illustrated in Figure 1. In addition $U_i = \{u_i\}, i\geq 2$, and $V_j = \{v_j\}$ are singletons.

Finally, we point out that for a given chain graph $G\cong {{\rm{CG}}}(\kappa, 1, 1, \ldots, 1;1, 1, \ldots, 1)$, the set of leaders $\mathit{\boldsymbol{\ell}}$ that makes the system (2.2) modeled by $G$ controllable can be simply determined by collecting $\kappa-1$ vertices with degree $h$. Consequently, an algorithm which determines the set of leaders should only test the vertex degrees (i.e., it collects $\kappa-1$ vertices of degree $h$).

5.   Conclusions

This paper covered the controllability of multi-agent dynamical systems modeled by a special class of bipartite graphs: Chain graphs with exactly one repeated degree. Chain graphs maximize the largest Laplacian eigenvalue in the set of connected bipartite graphs of a fixed order and size, and those with more than one repeated degree were considered in previous works ^[29,30]. In this study, all chain graphs with exactly one repeated degree were determined, along with the minimum number of leading agents and their positions in a graph. Accordingly, controllable systems with an arbitrary number of leading agents were constructed. In fact, for every fixed $\kappa$, a family of controllable bipartite systems with exactly $\kappa$ leaders was established by choosing a chain graph of height $h\leq\kappa$. Bearing in mind that the controllability of threshold graphs with the same structural property received attention in ^[31], we may say that the results of this paper can be considered as a bipartite counterpart to those of the mentioned reference. Our contribution may also be meaningful in creating new multi-agent controllable systems based on the graph Laplacian.

It has been shown that the algebraic connectivity of graphs considered lied in the interval $[\xi, \, 1]$, where $\xi$ was the algebraic connectivity of ${{\rm{CG}}}(2, 1;1, 1)$ and $1$ was attained only in a simple case heighted 1. Determining a fixed range for this spectral invariant is of particular interest since it gives an insight into the graph structure by measuring the reachability between the vertices and, in general, the robustness and synchronization of the entire graph. Moreover, for the considered class, the algebraic connectivity increased with the order, which is a rare phenomenon for the known controllable graph classes.

The obtained results suggest that the controllability of corresponding systems does not depend on the number of vertices of the entire graph, but only on those with equal degrees. Information on Laplacian eigenspaces of the graph permit the examination of the controllability, both locally and efficiently. Specifically, the minimum number of leaders which rendered the graph controllable equaled the largest multiplicity of the Laplacian eigenvalues. However, the limitations of the current research are related to the very particular structure of the considered class. A possible direction for the future research efforts would be to seek other graphs which possess similar properties, in particular, being controllable and having one repeated degree.

We conclude the discussion with a conjecture based on Corollary 3.4.

Conjecture 5.1. Let $G\cong {{\rm{CG}}}(m_1, m_2, \ldots, m_h; n_1, n_2, \ldots, n_h)$, for $\kappa\geq h\geq 2$. Additionally, let

be the sequence of vertex degrees of $G$ whose elements are $d_i, d_i^*, 1\leq i\leq h$, and $Q$ the divisor matrix of $G$ given in (2.5). Then, $G$ has no eigenvalues in $(d_{h-1}', d_h')\cup (d_h', d_{h+1}')$. In addition, for every $i\in \{1, 2, \ldots, 2h-1\}\setminus\{ h-1, h\}$, there exists an eigenvalue of $Q$ in $(d_i', d_{i+1}')$, and $d_1'$ does not exceed the largest Laplacian eigenvalue.

This work is an extended version of ^[44] presented on the IX International Conference IcETRAN and LXVI ETRAN Conference (Novi Pazar, Serbia, 2022).

Author contributions

All authors contributed equally and approved the final version of the manuscript.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.