# Minimum leader selection for Structural Controllability of Undirected Graphs
with Leader-follower Framework

Li Dai
College of Liberal Arts and Sciences,
National University of Defense Technology, Changsha 410072, China
<EMAIL_ADDRESS>
abstract The optimization problem of the minimum set of leaders for the
controllability of undirected graphs are addressed. It is difficult to find
not only its optimal solution but also its approximate algorithm. We propose a
new concept, namely minimal perfect critical set (MPCS), to obtain an optimal
solution. Some properties are presented, and on the basis of these theorems,
the problem of the minimum set of leaders of two typical self-similar
bipartite networks, namely deterministic scale-free networks (DSFN) and Cayley
trees, is solved completely.

keyword Controllability, undirected graph; minimum leader selection; minimal
perfect critical set; tree graph

##  1 Introduction

In recent years, the controllability of undirected networks has attracted
considerable attention. In contrast to the various insights and results on the
controllability of directed networks, there remain many basic problems that
need to be investigated with regard to the controllability of undirected
networks. For example, to ensure the controllability of an undirected network,
it is necessary to determine how to select the leader (leaders), what is the
minimum number of leaders, how to get the minimum set of leaders, and how
large is the minimum set of leaders. These problems are interesting because of
their potential application to various fields such as complex networks, multi-
agent systems, and biology.

###  1.1 Literature Review

Our goal is to address the problem of how to select leaders and how to obtain
the minimum number and minimum set of leaders of Laplacian-based leader-
follower undirected systems. Therefore, we review only the related studies.
The networks mentioned throughout this paper are undirected networks, unless
stated otherwise.

Research on the controllability of undirected network began with the work of
Tanner [1], where both a leader-follower framework and a Laplacian matrix were
considered to understand how the network structure and leader’s location
affect the controllability of a network. Many studies have been conducted
since then. The methods used in this field mainly include spectral analysis,
equitable partitions, zero forcing sets, balancing sets (see [17]), and
constraint matching.

The necessary or sufficient algebraic conditions of the leader set in view of
eigenvectors were presented for the controllability of a general network in
[2]-[6]. Owing to the existence of multiple eigenvalues and the need to
examine eigenvectors with zero components, it is computationally difficult to
directly use the algebraic conditions to find the set of leaders. Therefore,
network controllability based on the leader’s graphical structure has
attracted widespread attention.

In [7], the authors applied the concept of equitable partitions to the study
of controllability and pointed out that some vertex sets with a symmetric
character should not be selected as leaders. The necessary graph-theoretic
conditions for controllability involving equitable partitions or almost
equitable partitions were subsequently reported; see, for instance, [8]-[11].

The necessary/sufficient conditions for controllability based on (generalized)
zero forcing sets have been established in the literature [12]-[18]. In these
studies, a one-to-one correspondence was established between the set of
leaders rendering the network controllable and the zero forcing sets.

Some studies, such as [16],[19]-[20], have focused on constraint matching to
investigate controllability. A single leader and multiple leaders have been
considered in [19] and [20], respectively. The relationship between zero
forcing sets and constraint matching was discussed in [16].

Special topologies have been considered in some studies, such as trees
[28]-[29], grids [30], and circulants [31].

The above-mentioned studies constitute the profound literature on the
theoretical research of controllability. Some other studies are devoted to
algorithm design. As pointed out in several studies, finding a minimal zero
forcing set (see [16] ) or finding a minimum leader set (see[20]) for a
general network is an NP-hard problem, as is finding an approximate solution
(see [18]). Moreover, there are several different concepts of controllability
in the field of network controllability, such as controllability as defined by
Kalman in [21], structural controllability (defined by Lin in [22]), and
strong structural controllability (defined by Mayeda and Yamada in [23]). The
matrix can be defined as the adjacency matrix or Laplacian matrix with
variable or fixed parameters. Thus, research on the controllability of
networks is extensive.

Different from the existing studies, this paper proposes the concept of a
minimal perfect critical set (MPCS) in section 2. In addition, it presents the
necessary and sufficient conditions for $S$ to be a minimal perfect critical 2
set and proves an interesting result that a minimal perfect critical 3 set
does not exist. Section 3 constitutes the main part of this paper. It presents
some special MPCS of tree graphs. Section 4 presents three examples to
illustrate how to use the theories proposed to find MPCS . Finally, Section 5
concludes the paper.

###  1.2 Notations and Preliminary Results

Let $G=(V,E)$ be an undirected and unweighted simple graph, where
$V=\\{v_{1},v_{2},\cdots,v_{n}\\}$ is a vertex set and
$E=\\{v_{i}v_{j}|v_{i}\,\,and\,\,v_{j}\in V\\}$ is an edge set, where an edge
$v_{i}v_{j}$ is an unordered pair of distinct vertices in $V$. If
$v_{i}v_{j}\in E$, then $v_{i}$ and $v_{j}$ are said to be adjacent or
neighbors. $N_{S}(v_{i})=\\{v_{j}\in S|v_{i}v_{j}\in E(G)\\}$ represents the
neighboring set in $S$ of $v_{i}$, where $S\subset V$. The cardinality of $S$
is denoted by $|S|$. $d_{G}(v)$ is the degree of vertex $v$ in $G$ and
$d_{G}(v)=|N_{V}(v)|$. If $d_{G}(v)=1$, then $v$ is called a pendent vertex.
$G[S]$ is the induced subgraph, whose vertex set is $S$ and edge set is
$\\{v_{i}v_{j}\in E(G)|v_{i},v_{j}\in S\\}$. The valency matrix $\Delta(G)$ of
graph $G$ is a diagonal matrix with rows and columns indexed by $V$, in which
the $(i,i)$-entry is the degree of vertex $v_{i}$, e.g., $|N_{V}(v_{i})|$. Any
undirected simple graph can be represented by its adjacency matrix, $D(G)$,
which is a symmetric matrix with 0-1 elements. The element in position $(i,j)$
in $D(G)$ is 1 if vertices $v_{i}$ and $v_{j}$ are adjacent and 0 otherwise.
The symmetric matrix defined as

$\mathbf{L}(G)=\mathbf{\Delta}(G)-\mathbf{D}(G)$

is the Laplacian  of $G$. Throughout this paper, it is assumed without loss of
generality that $F$ denotes a follower set; its vertices play the role of
followers and the vertices in $\overline{F}$ are leaders(driver nodes), where
$\overline{F}=V\backslash F$ denotes the complement set of $F$. Let
$\mathbf{y}$ be a vector and $\mathbf{y}_{S}$ denote the vector obtained from
$\mathbf{y}$ after deleting the elements in $\overline{S}$. Let
$\mathbf{L}_{S\rightarrow T}$ denote the matrix obtained from $\mathbf{L}$
after deleting the rows in $\overline{S}$ and columns in $\overline{T}$. If
the followers’ dynamics is (see (4) in [1])

$\dot{\mathbf{x}}=\mathbf{Ax}+\mathbf{Bu},$

where $\mathbf{x}$ is the vector of all $x_{i}$ corresponding to follower
$v_{i}\in F$ and $\mathbf{u}$ is the external control input vector that is
injected to only leaders, then, the system is controllable if and only if the
$N\times NM$ controllability matrix

$\mathbf{C}=[\mathbf{B},\mathbf{AB},\mathbf{A^{2}B},\cdots,\mathbf{A^{N-1}B}]$

has full row rank, where $\mathbf{B}=\mathbf{L}_{F\rightarrow\overline{F}}$
and $\mathbf{A}=\mathbf{L}_{F\rightarrow F}$. This mathematical condition for
controllability is well known as Kalman’s controllability rank condition [21,
24, 26]. In terms of eigenvalues and eigenvectors of Laplacian submatrices, a
necessary and sufficient algebraic condition on controllability was presented
in [2] and [6](see Proposition 2,1(2) in [2] and Proposition 1 in [6] ).

######  Proposition 1.

[2, 6] The undirected graph $G$ is controllable under the leader set
$\overline{F}$ if and only if $\mathbf{y}|_{\overline{F}}\neq\mathbf{0}$ (
$\forall\,\,\mathbf{y}$ is an eigenvector of $\mathbf{L}$).

According to Proposition 1, for any $S\subset V$ and $S\neq\emptyset$, if
there exists an eigenvector y of Laplacian matrix L such that
$\mathbf{y}_{S}=\mathbf{0}$, then $S$ cannot be used as a leader set.

##  2 Minimal Perfect Critical Set

For a vertex set $S$, from Proposition 1, if there exist an eigenvector y such
that $\mathbf{y}_{\overline{S}}=\mathbf{0}$, then $\overline{S}$ should not be
used as a leaders set. In other words, there must be a vertex $v$ in $S$ to be
selected as a member of the leaders set. Therefore, to locate the leaders of
graph $G$, three new concepts are proposed.

######  Definition 1.

(critical set) Let $S$ be a nonempty subset of $V$. If there exists an
eigenvector y such that $\textbf{y}_{\overline{S}}=\textbf{0}$, then $S$ is
called a critical set(CS) and y is a inducing eigenvector. $S$ is called a
critical $k$ set if $|S|=k$.

######  Definition 2.

(perfect critical set) Let $S$ be a critical set. If there exists an
eigenvector y satisfying $\textbf{y}_{v_{i}}\neq 0(\forall v_{i}\in S)$, then
$S$ is called a perfect critical set (PCS). $S$ is called a perfect critical
$k$ set if $|S|=k$.

######  Definition 3.

(minimal perfect critical set) A perfect critical set is called a minimal
perfect critical set (MPCS) if any proper subset of it is no longer a PCS. $S$
is called a minimal perfect critical $k$ set if $|S|=k$.

From the definitions stated above, $V$ is a trivially CS and a PCS induced by
the eigenvector $\textbf{1}_{n}$. $V$ is an MPCS if and only if $G$ is
controllable under any single vertex selected as a leader; e.g., $G$ is
omnicontrollable.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{7}$$v_{6}$$v_{5}$ Figure 1: Graph $G$ with 4
distinct MPCS

For example, see Fig.1. $\\{v_{1},v_{5}\\}$ is not a CS;
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ is a CS but not a PCS.
$S=\\{v_{1},v_{2},v_{3}\\}$ is a PCS but not an MPCS.
$S_{1}=\\{v_{1},v_{2}\\}$, $S_{2}=\\{v_{1},v_{3}\\}$,
$S_{3}=\\{v_{2},v_{3}\\}$, and $S_{4}=\\{v_{5},v_{7}\\}$ are all MPCS.

######  Remark 1.

Proposition 1 can be restated as follows: The undirected graph $G$ is
controllable under the leader set $\overline{F}$ if and only if, for each MPCS
$S$ , $S\bigcap\overline{F}\neq\emptyset$.

From Remark 1 , there is a close relationship between MPCS and the minimum
leader set. In other words, when we find all MPCS of $G$, we find the minimum
leader set and hence the minimum number of leader vertices. For example, by
Remark 1 and the 4 MPCS stated above, graph $G$ in Fig.1 is not controllable
under any single leader because $\bigcap_{i=1}^{4}S_{i}=\emptyset$ , or under
any two vertices. Therefore, the minimum leader set is
$\\{v_{i},v_{j},v_{k}\\}$, where $v_{i},v_{j}$ comes from
$\\{v_{1},v_{2},v_{3}\\}$ and $v_{k}$ comes from $\\{v_{5},v_{7}\\}$.
Therefore, the minimum number of leaders is 3.

Moreover, many MPCS have typical graphical characteristics. For example, all
of the 4 MPCS of $G$ in Fig.1 have the graphical structure stated in Theorem
1.

###  2.1 Sufficient conditions for Critical Set

For an undirected connected graph, Laplacian matrix L is symmetric and all the
eigenvectors corresponding to different eigenvalues are orthogonal to each
other. Hence, by knowing that $\textbf{1}_{n}$ is an eigenvector of L, it is
immediate that all the other eigenvectors of L are orthogonal to
$\mathbb{1}_{n}$, i.e., for all eigenvectors $\mathbb{y}$,

$\textbf{1}_{n}^{T}\textbf{y}=\sum_{i=1}^{n}y_{i}=0.$ (1)

For all nontrivial graphs, if $S$ is a CS, then

$|S|\geq 2.$ (2)

In fact, suppose that $|S|=1$; without loss of generality, $S=\\{v_{1}\\}$.
Let $\textbf{y}=(y_{1},y_{2},\cdots,y_{n})^{T}$ be the inducing eigenvector
associated with eigenvalue $\lambda$. Then, $\textbf{Ly}=\lambda\textbf{y}$
and $\textbf{y}_{\overline{S}}=\textbf{0}$. By
$\textbf{y}_{\overline{S}}=\textbf{0}$ and (1), $\textbf{y}_{S}=\textbf{0}$,
e.g., $\textbf{y}=\textbf{0}$. Further, since any subset $S$ with $|S|=1$ is
not a CS, by Remark 1, $G$ is controllable with the leader set $\overline{F}$
when $|F|=1$. Now, we investigate the properties of a CS. First, a sufficient
condition for $S$ to be a CS is provided in the following Proposition 2, which
describes a special case of the symmetry-based uncontrollability results.

######  Proposition 2.

Let $G$ be an undirected connected graph of order $n$, $S\subset V$, and
$|S|\geq 2$. If for any $v\in\overline{S}$, either $N_{S}(v)=\emptyset$ or
$N_{S}(v)=S$, then $S$ is a critical set.

Proof Let $|\\{v\in\overline{S}|N_{S}(v)=S\\}|=m$. Then,
$\textbf{L}_{S\rightarrow S}-m\textbf{I}_{|S|}$ is the Laplacian of subgraph
$G[S]$, where $\textbf{I}_{|S|}$ denotes the $|S|$-dimensional identity
matrix. Considering (1), there exists an eigenvector $\textbf{y}_{0}$ of the
Laplacian $\textbf{L}_{S\rightarrow S}-m\textbf{I}_{|S|}$ such that
$\textbf{1}_{|S|}^{T}\textbf{y}_{0}=0$.

Set vector y as $\textbf{y}_{S}=\textbf{y}_{0}$ and
$\textbf{y}_{\overline{S}}=\textbf{0}$. It can be seen that

$\textbf{Ly}=\left[\begin{array}[]{ll}\textbf{L}_{S\rightarrow
S}&\textbf{L}_{S\rightarrow\overline{S}}\\\
\textbf{L}_{\overline{S}\rightarrow
S}&\textbf{L}_{\overline{S}\rightarrow\overline{S}}\end{array}\right]\left[\begin{array}[]{c}\textbf{y}_{0}\\\
\textbf{0 }\end{array}\right]=\left[\begin{array}[]{c}\lambda\textbf{y}_{0}\\\
\textbf{L}_{\overline{S}\rightarrow S}\textbf{y}_{0}\end{array}\right].$ (3)

Noting that the rows in matrix $\textbf{L}_{\overline{S}\rightarrow S}$ are
either ones or zeros, the conclusion is proved by
$\textbf{1}_{|S|}^{T}\textbf{y}_{0}=0$(see (1)). ∎

###  2.2 Minimal Perfect Critical 2 and 3 Set

Based on the above-mentioned properties, the critical $k$ set with $k\leq 3$
can be determined directly from the graphical characterization. This is
achieved via a detailed analysis of the inducing eigenvector.

######  Lemma 1.

Let $G$ be an undirected connected graph and $S$ be a perfect critical $k$
vertices set. Then, for any $v\in\overline{S}$, $|N_{S}(v)|\neq 1$ and
$|N_{S}(v)|\neq k-1$.

Proof Let $S=\\{v_{1},v_{2},\cdots,v_{k}\\}$ be a perfect critical vertex set
and $\textbf{y}=(y_{1},y_{2},\cdots,y_{k},0,0,\cdots,0)^{T}$ be the inducing
eigenvector. $y_{i}\neq 0(\forall 1\leq i\leq k)$ since $S$ is a perfect
critical vertex set. $\forall v\in\overline{S}$, suppose that $|N_{S}(v)|=1$.
Without loss of generality, say, $vv_{1}\in E$ and $vv_{i}\notin E(G)(\forall
i\neq 1)$. Then, $\textbf{L}_{\\{v\\}\rightarrow V}\textbf{y}=y_{1}\neq 0$. On
the other hand, $\textbf{y}|_{\overline{S}}=\textbf{0}$ and
$v\in\overline{S}$. Hence, $\textbf{L}_{\\{v\\}\rightarrow V}\textbf{y}=0$.
This is a contradiction. Together with (1), $|N_{S}(v)|\neq k-1$ can be proved
similarly.∎

By (2), a critical 2 set is also a minimal perfect critical 2 set. The
following Theorem 1 will follow from Lemma 1 and Proposition 2.

######  Theorem 1.

Let $G$ be an undirected connected graph, $S\subset V$, and $|S|=2$. Then, $S$
is a minimal perfect critical 2 set if and only if $\forall v\in\overline{S}$,
either $N_{S}(v)=\emptyset$ or $N_{S}(v)=S$.∎

For example, see graph $G$ in Fig.1. All its 4 MPCS can be recognized by the
graphical characterization stated in Theorem 1.

Next, we will prove that a minimal perfect critical 3 set does not exist in
the following theorem.

######  Theorem 2.

Let $G$ be an undirected connected graph, $S\subset V$, and $|S|=3$. Then, $S$
is not a minimal perfect critical set.

Proof Suppose that $S$ is a minimal perfect critical set. Consider the
subgraph $G[S]$. All 4 possible topology structures of $G[S]$ are shown in
Fig. 2.

Figure 2: All possible topology structures of $G[S]$ with $|S|=3$

For each topology of $G[S]$ in Fig.2, let $T$ be the vertex set of white
vertices and $u$ be the black vertex. One can have either $N_{T}(u)=\emptyset$
or $N_{T}(u)=T$.

By Lemma 1, $\forall v\in\overline{S}$, either $|N_{S}(v)|=0$ or
$|N_{S}(v)|=3$.

Noting that $T\subset S$ and $\overline{T}=\\{u\\}\bigcup\overline{S}$, by
Proposition 2, $T$ is a critical set. This is in contradiction with $S$ as a
MPCS.∎

$S_{1}$$(a)\,\,S_{1}$is minimal perfect critical set$S_{2}$$(b)\,\,S_{2}$is
not a critical set Figure 3: Topology structure effect on MPCS when $|S|\geq
4$

Although a minimal perfect critical 3 set does not exist, a minimal perfect
critical 4 set does exist; see Fig.3(a). The topology structure of $G[S]$ will
affect whether $S$ is an MPCS; see Fig.3.

##  3 Minimal Perfect Critical Set of Trees

In this section, we first introduce a method for the simplification of $G$ and
then prove some properties of MPCS of trees.

###  3.1 Simplification Graph $\tilde{G}$

Let $S$ be a proper subset of $V(G)$. Let $\tilde{G}$ denote a graph
constructed in the following steps:

Initialize $\tilde{G}=G$.

①If $v\in\bar{S}$ and $N_{G}(v)\cap S=S$, then set $\tilde{G}:=\tilde{G}-v$.

②If $v\in\bar{S}$ and $N_{G}(v)\cap S=\emptyset$, then set
$\tilde{G}:=\tilde{G}-v$.

$S$ is a CS of a connected graph $G$ if and only if $S$ is a CS of
$\tilde{G}$. Further, $\lambda$ is the corresponding eigenvalue of
$\textbf{L}(G)$ if and only if $\lambda-1$,$\lambda$ is an eigenvalue of
$\textbf{L}(\tilde{G})$ in case ①, ②, respectively.

###  3.2 Necessities of MPCS of Trees

######  Proposition 3.

If $S$ is a CS of tree graph $G$, then there are at least 2 pendent vertices
in $S$.

Proof Let $v_{0}\in\bar{S}$ be a pendent vertex in tree $G$ and $u_{0}$ be the
vertex adjacent to $v_{0}$. By Lemma 1, we have $u_{0}\in\bar{S}$. Hence, $S$
is still a PCS of tree graph $G-v_{0}$. Set $\bar{S}_{1}:=\bar{S}-v_{0}$,
$G_{1}:=G-v_{0}$. It is useful to note that $d_{G}(v)=d_{G_{1}}(v)(\forall
v\in S)$. Repeat these steps to obtain a tree graph $G^{\prime}$ with
$d_{G^{\prime}}(v)>1(\forall v\in\bar{S})$. It is well known that there are at
least two pendent vertices in a tree graph. Considering the tree graph
$G^{\prime}$, we know that the pendent vertices are all in $S$. This completes
the proof. ∎

By Remark 1 and Proposition 3, we have the following theorem:

######  Theorem 3.

Let $S_{0}=\\{v\in V(G)|d_{G}(v)=1\\}$ and $F$ be a follower set. If $|F\cap
S_{0}|\leq 1$, then tree graph $G$ is controllable under leader set
$\bar{F}$.∎

Theorem 3 tells us that when $|S_{0}|-1$ vertices in $S_{0}$ are selected as
leaders, the graph will be controllable. Therefore, the minimum number of
leaders is no more than $|S_{0}|-1$.

Next, we will study the property that the MPCS of trees should have.

######  Proposition 4.

If $S$ is a nontrivial PCS of tree graph $G$, then $G[S]$ is a disconnected
subgraph.

Proof Suppose that $G[S]$ is a connected subgraph. Arbitrarily take a vertex
$v$ in $\bar{S}$. By Lemma 1, there exist at least two vertices in $S$, say
$u_{1},u_{2}$ such that $vu_{i}\in E(G)(i=1,2)$. Since $G[S]$ is connected,
there exists a circle $C$ with $u_{1},u_{2},v\in V(C)$ in $G$, and this is a
contradiction to $G$ being a tree. ∎

######  Proposition 5.

If $S$ is a nontrivial MPCS of tree graph $G$, then $\tilde{G}[\bar{S}]$ is a
graph of isolated vertices.

Proof Suppose that there exists a component $T$ of $\tilde{G}[\bar{S}]$ that
contains at least two vertices. See Fig.4.

$S$$\bar{S}$$S_{u}$$S_{1}$$T$$w$$v$$u$$\times$[500](37,8)(39,7)(40,30)(41,47.5)
[500](37,8)(35,7)(28,30)(27.3,47.5) [500](10,8)(12,9)(25,30)(26.7,47.5)
[500](56,8)(57,9)(60,40)(69,47.5)  Figure 4: Component $T$ of
$\tilde{G}[\bar{S}]$ with at least two vertices

Then, $T$ is a tree graph and there exist at least two pendent vertices of
$T$, say $u,v$. Let $P_{uv}$ be the $(u,v)$-path in $T$ and $wv\in E(P_{uv})$.
Considering the disconnected graph $\tilde{G}-wv$, it is seen that $u$ and $v$
belong to different components. Let $T_{1}$ be the component that contains
$u$. Let $S_{u}=V(T_{1})\cap S$ and set

$S_{1}=S-S_{u}.$

We claim that $S_{1}$ is a PCS. In fact, $S_{u}$ and $S_{1}$ belong to
different components of $\tilde{G}-wv$. Hence, the submatrix
$\textbf{L}_{S_{1}\rightarrow S_{u}}=\textbf{0}$. Further, set y as the
inducing eigenvector of MPCS $S$. Then, set
$\tilde{\textbf{y}}=(\textbf{y}_{S_{1}},\textbf{0})$. For each
$v^{\prime}\in\bar{S}$, either $N_{\tilde{G}-wv}(v^{\prime})\cap S\subseteq
S_{u}$ or $N_{\tilde{G}-wv}(v^{\prime})\cap S\subseteq S_{1}$. Therefore,
$\tilde{\textbf{y}}$ is the inducing eigenvector of $S_{1}$.

Since $S_{1}$ is a PCS and $S_{1}\subset S$, it is contradictory to the fact
that $S$ is an MPCS.∎

######  Proposition 6.

If $S$ is an MPCS of tree graph $G$, then $d_{\tilde{G}}(v)=2(\forall
v\in\bar{S})$.

Proof From Lemma 1, $d_{\tilde{G}}(v)\neq 1(\forall v\in\bar{S})$. From
Proposition 5, $N_{V(\tilde{G})}(v)\subset S(\forall v\in\bar{S})$. Suppose
that there exists a vertex in $\bar{S}$ , say $u$ , such that
$d_{\tilde{G}}(u)\neq 2$, i.e. $d_{\tilde{G}}(u)>2$. (see Fig.5). Considering
the subgraph $\tilde{G}-u$, different vertices that are adjacent to $u$ belong
to different components of $\tilde{G}-u$. Let $T_{i}$ be the component and
$v_{i}\in V(T_{i})(i=1,2)$. Let $S_{i}=S\cap V(T_{i})(i=1,2)$. Since $G$ is a
tree graph, we have $S_{1}\cap S_{2}=\emptyset$. Let $\tilde{S}=S_{1}\cup
S_{2}$. From $d_{\tilde{G}}(u)>2$, we know that $\tilde{S}$ is a proper subset
of $S$.

We claim that $\tilde{S}$ is a PCS. In fact, let y be the inducing eigenvector
of MPCS $S$, where $y_{i}$ are its elements corresponding to $v_{i}(i=1,2)$
and $\textbf{y}_{S_{i}}$ are its elements corresponding to $S_{i}$. Let

$\textbf{y}_{\tilde{S}}=\left[\begin{array}[]{c}\frac{\textbf{y}_{S_{1}}}{y_{1}}\\\
\\\ -\frac{\textbf{y}_{S_{2}}}{y_{2}}\end{array}\right].$

Then, we have
$\textbf{L}_{\tilde{S}\rightarrow\tilde{S}}\textbf{y}_{\tilde{S}}=\lambda\textbf{y}_{\tilde{S}}$
and
$\textbf{L}_{\bar{\tilde{S}}\rightarrow\tilde{S}}\textbf{y}_{\tilde{S}}=\textbf{0}.$
Therefore, $[\textbf{y}_{\tilde{S}},\textbf{0}]$ is a inducing eigenvector for
$\tilde{S}$ to be a PCS. This is a contradiction to the fact that $S$ is an
MPCS since $\tilde{S}$ is a proper subset of $S$.∎

$u$$v_{2}$$S_{2}$$v_{1}$[500](32.8,20.6)(32,25)(33,49)(34.5,47)
$S_{1}$vertices in $\bar{S}$vertices in $S$ Figure 5: Vertex $u\in\bar{S}$
with $d_{\tilde{G}}(u)>2$

###  3.3 No Isolated MPCS with $|S|\geq 3$ in Trees

In this subsection, it is proved that there is no MPCS with isolated vertex
set $S(|S|\geq 3)$ for tree graph.

######  Theorem 4.

Let $S$ be an isolated vertex set of tree graph $G$ and $|S|\geq 3$. Then, $S$
is not an MPCS.

Proof Suppose that $S$ is an MPCS and it is an isolated vertex set. Then,
$\textbf{L}_{S\rightarrow S}$ is a diagonal matrix. By
$\textbf{L}_{S\rightarrow S}\textbf{y}_{S}=\lambda\textbf{y}_{s}$, we know
that $d_{G}(v)=\lambda(\forall v\in S)$. Thus, all vertices in $S$ have the
same degree.

On the other hand, from Proposition3, there exist at least two vertices in $S$
with degree 1. Hence, we have $d_{G}(v)=1(\forall v\in S).$

Noting that $\tilde{G}[S\cup\bar{S}]$ is a tree graph and from Proposition 6,
we have

$|S|+2|\bar{S}|=\sum d_{i}=2\epsilon=2(|S|+|\bar{S}|-1).$

Hence, $|S|=2$. This is a contradiction to $|S|\geq 3.$ ∎

From Theorem 4 and Theorem 1, for the tree graph, the isolated vertex set $S$
is an MPCS if and only if $|S|=2$ and the two vertices in $S$ are twin nodes.

###  3.4 A Type of Special MPCS of Trees

Considering the Laplacian matrix of graph $\tilde{G}$, similar to the proof of
Theorem 4, it is seen that the following proposition holds.

######  Proposition 7.

Let $S$ be a CS of tree graph $G$. If there exists a vertex $v_{0}\in S$ such
that $d_{\tilde{G}[S]}(v_{0})=0$, and $d_{\tilde{G}}(v_{0})=t$, then the
corresponding eigenvalue $\lambda=t$ and $d_{\tilde{G}}(v)=t(\forall v\in
S:d_{\tilde{G}[S]}(v)=0).\qed$.

######  Proposition 8.

Let $S$ be an MPCS of tree graph $G$. If there exists a vertex $v_{0}\in S$
such that $d_{\tilde{G}[S]}(v_{0})=0$, and $d_{\tilde{G}}(v_{0})=1$ for each
$v$ with $d_{\tilde{G}}(v)=1$ and $u_{v}v\in E(\tilde{G})$, then
$u_{v}\in\bar{S}$.

Proof By contrast, suppose that $u_{v}\in S$. Then, by Lemma 1, we have
$v\notin\bar{S}$. Hence, $v\in S$. From Proposition 7, we know that
$\lambda=1$. Since $\textbf{L}_{v\rightarrow
V(\tilde{G})}\textbf{y}=\lambda\textbf{y}_{v}=\textbf{y}_{v}$,
$\textbf{y}_{v}-\textbf{y}_{u_{v}}=\textbf{y}_{v}$ and $\textbf{y}_{u_{v}}=0$.
This is a contradiction to $u_{v}\in S$ and $S$ is an MPCS. ∎

To prove the next property of MPCS, we first give the following lemma.

######  Lemma 2.

Let $\textbf{A}=(a_{ij})_{n\times n}$ be a Laplacian matrix of a tree graph.
Matrix $\textbf{B}=(b_{ij})_{n\times n}$, where
$b_{ij}=\left\\{\begin{array}[]{ll}a_{ij}+c_{i},&i=j,\\\ a_{ij},&i\neq
j,\end{array}\right.c_{i}\in\\{-1,0\\}$. Then, there exists a vector
$\textbf{X}_{0}=(x_{1},x_{2},\cdots,x_{n})^{\mathrm{T}}(\forall i,x_{i}\neq
0)$ such that $\textbf{BX}_{0}=\textbf{0}$ if and only if
$c_{1}=c_{2}=\cdots=c_{n}=0$.

Proof $(\Leftarrow)$ If $c_{1}=c_{2}=\cdots=c_{n}=0$, then
$\textbf{B}=\textbf{A}$ is a Laplacian matrix and
$\textbf{X}_{0}=(1,1,\cdots,1)^{\mathrm{T}}$. $(\Rightarrow)$ By induction on
the order $n$.

If $n=1$, then $a_{11}=0$ and $(a_{11}+c_{1})x_{1}=0$. Hence, $c_{1}=0$ since
$x_{1}\neq 0$.

Assume that the lemma is true for each matrix of order lower than $n(n\geq
2)$.

Let $T$ be the given tree with $n$ vertices and $A$ be its Laplacian matrix.
Let $v_{1}$ be a pendent vertex in $T$ and $v_{2}$ be the only vertex adjacent
to $v_{1}$. Then, matrix $A$ and matrix $B$ have the following form:

$\textbf{A}=\left[\begin{array}[]{ccccc}1&-1&0&\cdots&0\\\
-1&a_{22}&a_{23}&\cdots&a_{2n}\\\ 0&a_{32}&a_{33}&\cdots&a_{3n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&a_{n2}&a_{n3}&\cdots&a_{nn}\end{array}\right],$
$\textbf{B}=\left[\begin{array}[]{ccccc}1+c_{1}&-1&0&\cdots&0\\\
-1&a_{22}+c_{2}&a_{23}&\cdots&a_{2n}\\\ 0&a_{32}&a_{33}+c_{3}&\cdots&a_{3n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&a_{n2}&a_{n3}&\cdots&a_{nn}+c_{n}\end{array}\right].$

Let $\textbf{X}_{0}=(x_{1},x_{2},\cdots,x_{n})(\forall i,x_{i}\neq 0)$ and
$\textbf{BX}_{0}=\textbf{0}$. From the first row of
$\textbf{BX}_{0}=\textbf{0}$,

$(1+c_{1})x_{1}-x_{2}=0.$

If $c_{1}=-1$, then $x_{2}=0$ and this is a contradiction. Hence, $c_{1}=0$
and $x_{1}=x_{2}$.

By elementary row transformation on matrix B,

$\textbf{B}\xrightarrow{r_{2}:=r_{1}+r_{2}}\left[\begin{array}[]{cc}1&\cdots\\\
\vdots&\textbf{B}^{\prime}\end{array}\right].$

The second row of $\textbf{BX}_{0}=\textbf{0}$ and $x_{1}=x_{2}$ implies that
$\textbf{B}^{\prime}\textbf{X}^{\prime}_{0}=\textbf{0},$ where
$\textbf{X}^{\prime}_{0}=(x_{2},x_{3},\cdots,x_{n})^{\mathrm{T}}.$ Noting that
matrix $\textbf{B}^{\prime}$ is of order $n-1$, we have
$c_{2}=c_{3}=\cdots=c_{n}=0$. ∎

$c_{1}=c_{2}=\cdots=c_{n}=0$ means $\mathbf{B}=\mathbf{A}$, that is
$\mathbf{B}$ is the Laplacian matrix of tree graph.

Next, we will prove the following theorem to provide a graphical
characterization of a special type of MPCS.

######  Theorem 5.

Let $G$ be a tree graph and $S\subset V(G)$. If there exists a vertex
$v_{0}\in S$ such that $d_{\tilde{G}[S]}(v_{0})=0$, and
$|N_{\tilde{G}}(v)\cap\bar{S}|\leq 1(\forall v\in S)$, then $S$ is an MPCS if
and only if $N_{\tilde{G}}(v)\cap\bar{S}=1(\forall v\in S)$.

Proof $(\Rightarrow)$ We only need to prove that
$d_{\tilde{G}}(v)=d_{\tilde{G}[S]}(v)+1(\forall v\in S).$

Since $S$ is an MPCS, $\tilde{G}$ is connected. Hence, for vertex $v_{0}$,
from $|N_{\tilde{G}}(v)\cap\bar{S}|\leq 1$, we have $d_{\tilde{G}}(v_{0})=1$.
By Proposition 7, the corresponding eigenvalue $\lambda=1$ and
$d_{\tilde{G}}(v)=1(\forall v\in S:d_{\tilde{G}[S]}(v)=0).$ Therefor, only the
vertices $v\in S$ with $d_{\tilde{G}[S]}(v)>0$ needed to be considered.

Let $v$ belong to $\tilde{G}_{i}$(tree), which is the $i$-th component of the
subgraph $\tilde{G}[S]$. Let $S_{i}=V(\tilde{G}_{i})$ and let
$\textbf{L}^{\tilde{G}}$ , $\textbf{L}^{\tilde{G}[S]}$ denote the Laplacian
matrix of graph $\tilde{G}[S\cup\bar{S}]$, $\tilde{G}[S]$, respectively.

Since $S$ is an MPCS, we know that there exists an eigenvector y such that
$\textbf{y}_{v}\neq 0(\forall v\in S)$ and
$\textbf{L}^{\tilde{G}}_{S_{i}\rightarrow
S_{i}}\cdot\textbf{y}_{S_{i}}=\lambda\textbf{y}_{S_{i}}=\textbf{y}_{S_{i}}(\lambda=1).$
Thus, $(\textbf{L}^{\tilde{G}}_{S_{i}\rightarrow
S_{i}}-\textbf{I})\cdot\textbf{y}_{S_{i}}=\textbf{0}.$ By Lemma 2, we have

$\textbf{L}^{\tilde{G}}_{S_{i}\rightarrow
S_{i}}-\textbf{I}=\textbf{L}^{\tilde{G}[S]}_{S_{i}\rightarrow S_{i}},$ (4)

and this completes the proof of necessity.

$(\Leftarrow)$ If $v$ is a pendent vertex in $\tilde{G}$, then
$d_{\tilde{G}[S]}(v)=0$. From Proposition 3 and Proposition 7, we know that
the corresponding eigenvalue $\lambda=1$ for any PCS
$S^{\prime}(S^{\prime}\subseteq S)$.

To prove the sufficiency, we need to prove that there exists only one linearly
independent vector y (corresponding eigenvalue $\lambda=1$) such that

$\textbf{L}^{\tilde{G}}\cdot\textbf{y}=\textbf{y},$ (5) $\textbf{y}_{v}\neq
0(\forall v\in S),$ (6) $\textbf{y}_{v}=0(\forall v\in\bar{S}).$ (7)

We construct a new graph $H$ as follows. Let $u_{i}\in V(H)$ represent
$\tilde{G}_{i}$, where $\tilde{G}_{i}$ is the $i$-th component of
$\tilde{G}[S]$ and $w_{j}\in V(H)$, and let represent the $j$-th vertex in
$\bar{S}$. $E(H)=\\{u_{i}w_{j}|$ the $j$-th vertex in $\bar{S}$ is adjacent to
one of vertices in $\tilde{G}_{i}\\}$. $H$ is a tree graph. Let $u_{0}$
correspond to $v_{0}$ and let it be a pendent vertex in $H$. Set

$\textbf{y}_{u_{0}}=1,\textbf{y}_{v}=0(\forall v\in\bar{S}).$

According to Proposition 4, $u_{i}(i\geq 1)$ exists. $\forall u_{i}(i\geq
1)\in V(H)$, there exists only one path between $u_{0}$ and $u_{i}$. Let
$l_{i}$ be the length of this path (i.e., the number of edges on this path).
By Proposition 6, $l_{i}$ is even. Set

$\textbf{y}_{v}=(-1)^{\frac{l_{i}}{2}}(\forall v\in V(\tilde{G}_{i})).$ (8)

It is easily seen that the vector y defined above satisfies (6) and (7).

$\forall w_{j}\in V(H)$, by Proposition 5 and Proposition 6, we know that
there exist exactly two vertices, say $u_{i_{1}}$ and $u_{i_{2}}$, such that
$u_{i_{k}}w_{j}\in E(H)(k=1,2)$. Hence, from (8), we have

$\textbf{L}^{\tilde{G}}_{v\rightarrow
V(\tilde{G})}\cdot\textbf{y}=1+(-1)=0=\textbf{y}_{v}(\forall v\in\bar{S}).$

$\forall u_{i}\in V(H)$, let $S_{i}=V(\tilde{G}_{i})$. Since
$\textbf{L}^{\tilde{G}[S]}_{S_{i}\rightarrow S_{i}}$ is the Laplacian matrix
of tree graph $\tilde{G}_{i}$, we know that $\textbf{y}_{S_{i}}$(see (8)) is
the only linearly independent vector such that

$\textbf{L}^{\tilde{G}[S]}_{S_{i}\rightarrow
S_{i}}\cdot\textbf{y}_{S_{i}}=\textbf{0}.$

By (4) and (1), we have

$\textbf{L}^{\tilde{G}}_{v\rightarrow
V(\tilde{G})}\cdot\textbf{y}=\textbf{y}_{v}(\forall v\in S).$

Hence, the vector y defined above satisfies (5). This completes the proof of
sufficiency. ∎

##  4 Simulations and Discussion

Finally, we illustrate the method for selecting leader vertices that render an
undirected graph controllable by using the theories presented above.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{15}$$v_{9}$$v_{13}$$v_{14}$$v_{10}$$v_{11}$$v_{12}$
Figure 6: Tree graph $G$

###  4.1  A Synthetic Tree

See Fig.6. All MPCS of $G$ can be found, and the process of finding MPCS is
shown in Table 1.

There are a total of three MPCS of $G$; they are
$\\{v_{6},v_{7}\\},\\{v_{6},v_{4},v_{3},v_{1},$
$v_{9},v_{14},v_{10},v_{12}\\},\\{v_{7},v_{4},v_{3},v_{1},v_{9},v_{14},v_{10},v_{12}\\}.$
Hence, from Remark 1, we know that the minimum number of leaders is 2 and
there are a total of 15 different minimum leader sets, i.e.,

$\\{v_{6},v_{7}\\}\,\,and\,\,\\{v_{i},v_{k}\\}(i\in\\{6,7\\},k\in\\{1,3,4,9,10,12,14\\}).$

Table 1: Process of finding MPCS vertex |  theory |  $S$ |  $\bar{S}$ |  MPCS
---|---|---|---|---
$v_{6},v_{7}$ |  Theorem 1 |  ✓ |  | $\\{v_{6},v_{7}\\}$
$v_{6}$ |  initial( or $v_{7}$) |  ✓ |  |
$v_{7}$ |  initial(or $v_{6}$) |  |  ✓ |
$v_{5}$ |  Lemma 1(see $v_{7}$) |  |  ✓ |
$v_{2}$ |  Proposition 8(see $v_{5},v_{6}$) |  |  ✓ |
$v_{8}$ |  Proposition 8(see $v_{5},v_{6}$) |  |  ✓ |
$v_{11}$ |  Proposition 8(see $v_{5},v_{6}$) |  |  ✓ |
$v_{13}$ |  Proposition 8(see $v_{5},v_{6}$) |  |  ✓ |
$v_{4}$ |  Proposition 6(see $v_{5}$) |  ✓ |  |
$v_{15}$ |  Lemma 1(see $v_{8}$) |  |  ✓ |
$v_{3}$ |  proof of Theorem 4(see $v_{4},v_{6}$) |  ✓ |  |
$v_{1}$ |  Proposition 6(see $v_{2}$) |  ✓ |  |
$v_{9}$ |  Proposition 6,Theorem 4(see $v_{10}$) |  ✓ |  |
$v_{14}$ |  Proposition 6(see $v_{13}$) |  ✓ |  |
$v_{10}$ |  Lemma 1(see $v_{9},v_{11}$) |  ✓ |  |
$v_{12}$ |  Proposition 6(see $v_{11}$) |  ✓ |  |
|  Theorem 5 |  |  |  $\\{v_{6}\\}\cup S^{\prime}$
|  Theorem 5 |  |  |  $\\{v_{7}\\}\cup S^{\prime}$

###  4.2 DSFN

A classical self-similar hierarchical network model called a deterministic
scale-free network (DSFN) was proposed in [32]. It is built in an iterative
manner; see Fig.7. Subsequently, in [33], the authors studied the nature of
the maximum eigenvalue in the spectrum of DSFN and showed that most of the
important quantities in network theory can be obtained analytically. By using
the graphical characterization of MPCS provided in this paper, we will
determine both its minimum number and minimum sets of leaders in a more
concise manner.

$1$$g=0$$1$$g=1$$2$$3$$1$$g=2$$2$$3$$4$$5$$6$$7$$8$$9$[300](54,56.5)(55,60)(57,70)(59.3,71)
[300](50,56.7)(50.5,70)(57,70.5)(59.3,71)
[300](66,56.7)(65.5,60)(63,70.5)(60.8,71)
[300](70,56.7)(69.5,70)(62,70.5)(60.8,71)
$1$$g=3$$2$$3$$4$$5$$6$$7$$8$$9$[300](54,26.5)(55,30)(57,40)(59.3,41)
[300](50,26.7)(50.5,40)(57,40.5)(59.3,41)
[300](66,26.7)(65.5,30)(63,40.5)(60.8,41)
[300](70,26.7)(69.5,40)(62,40.5)(60.8,41)
$10$$11$$12$$13$$14$$15$$16$$17$$18$[300](30,6.5)(31,10)(33,20)(35.3,21)
[300](26,6.7)(26.5,20)(33,20.5)(35.3,21)
[300](42,6.7)(41.5,10)(39,20.5)(36.8,21)
[300](46,6.7)(45.5,20)(38,20.5)(36.8,21)
$19$$20$$21$$22$$23$$24$$25$$26$$27$[300](78,6.5)(79,10)(81,20)(83.3,21)
[300](74,6.7)(74.5,20)(81,20.5)(83.3,21)
[300](90,6.7)(89.5,10)(87,20.5)(84.8,21)
[300](94,6.7)(93.5,20)(86,20.5)(84.8,21) [500](26,7)(27,39)(58,41.1)(59,41.1)
[500](30,7)(30,39)(58,41.1)(59,41.1) [500](42,7)(42,41)(58,41.1)(59,41.1)
[500](46,7)(43,41)(58,41.1)(59,41.1) [500](74,7)(77,41)(60,41.1)(61,41.1)
[500](78,7)(80,41)(60,41.1)(61,41.1) [500](90,7)(89,41)(59,41)(61,41.1)
[500](94,7)(93,41)(59,41.1)(61,41.1)  Figure 7: First four steps of
construction of the DSFN model $D(g)$

Let $D(g)$, $n_{l}$, and $n_{s}$ denote the $g$-th generation of the DSFN ,
the minimum number of leaders, and the number of minimum sets of leaders,
respectively.

By Theorem 1, $\\{3k-1,3k\\}(k=1,2,\cdots,3^{g-1})$ are MPCS of $D(g)$. Except
for these MPCS, $D(g)$ has no other MPCS. In fact, see the vertices labeled
$1,2,3$; if at least one of vertex $2,3$ belongs to $\bar{S}$, without loss of
generality, let $2\in S$ and $3\in\bar{S}$. Then, $1\in\bar{S}$(Lemma 1).
Similarly, all vertices with label $3k-2(k=1,2,\cdots,3^{g},g\geq 1)$ belong
to $\bar{S}$. Further, noting that all vertices labeled $3k-1,3k$ are only
adjacent to some vertices labeled $3j-2$, one can find that
$3k-1,3k(k=2,3\cdots,3^{g},g\geq 1)$ belong to $\bar{S}$. Therefore,
$S=\\{2\\}$, by (2), $S$ is not an MPCS.

These MPCS of $D(g)$ are pairwise disjoint; hence,
$n_{l}=3^{g-1},n_{s}=2^{n_{l}}.$ The total number of vertices of $D(g)$ is
$n=3^{g}$.

According to [34], the index $N_{1}$, defined as the ratio of $n_{l}$ to the
network size $n$, can be used to describe the level of network
controllability. For DSFN, the ratio is a constant,
$N_{1}=\frac{n_{l}}{n}=\frac{1}{3}.$ This indicates that it is necessary to
independently control at least one-third of the vertices to control the DSFN
fully.

Since we have obtained all the MPCS of $D(g)$, we introduce another index
$N_{2}$, which indicates the possibility of finding the minimum sets of
leaders. It is defined as the ratio of $n_{s}$ to the number of subsets of $V$
with $n_{l}$ elements. For $D(g)$,

$N_{2}(D(g))=\frac{n_{s}}{C_{n}^{n_{l}}}\leq(\frac{2}{3})^{n_{l}}\rightarrow
0(g\rightarrow\infty).$ (9)

Here, (9) suggests that it is extremely difficult to find the minimum set
without theoretical analysis, even if we know the minimum number, and the
probability rapidly decreases to 0.

###  4.3 Cayley Tree

$2$$4$$3$$g=1$$1$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$g=2$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$g=3$
Figure 8: First three steps of construction of Cayley tree $C(g)$

A Cayley tree is a classical model for dendrimers [35], which can be
constructed in an iterative manner; see Fig.8. Let $C(g)$ denote the Cayley
trees after $g$ generations. For any $g\geq 2$, $C(g)$ is built from $C(g-1)$.
For each pendent vertex of $C(g-1)$, two new vertices are created and linked
to the pendent.

The total number of vertices of $C(g)$ is $n=3\cdot 2^{g}-2$. Next, we will
determine all MPCS of $C(g)$. Some MPCS can be determined by Theorem 1. They
are the sets composed of two pendents that are adjacent to the same vertex. In
addition to these MPCS, there may be other MPCS. See Fig.9. Without loss of
generality, let $S$ be an MPCS with $1\in S$ and $2\notin S$. Then, by Theorem
1(see vertex 2), we have $6\notin S$. From Proposition 6, $7\in S$. Further,
$\lambda=1$ can be derived by Proposition 7. We claim that $9\in S$.
Otherwise, the vertex $7$ will be an isolated vertex in $G[S]$ and recall the
proof of Theorem 4; vertex 7 should have the same degree as vertex 1 in the
Cayley tree. Similarly, $8\in S$. From $\textbf{L}_{7\rightarrow
V}\textbf{y}_{S}=\lambda y_{7}$, we have $3y_{7}-y_{9}=y_{7}$, i.e.,
$y_{9}=2y_{7}$. Similarly, $y_{9}=2y_{8}$. From $\textbf{L}_{9\rightarrow
V}\textbf{y}_{S}=\lambda y_{9}$, we have $y_{9}=y_{11}$, i.e., $11\in S$.
Therefore, $10\in S$ and $y_{11}=y_{10}$. From $\textbf{L}_{11\rightarrow
V}\textbf{y}_{S}=\lambda y_{11}$, we have $12\notin S$. Then, one of
$\\{13,14\\}$ will belong to $S$. Thus far, we have obtained another MPCS $S$
of Cayley tree $C(g)(g\geq 5)$, where $S$ is composed of the vertices filled.

$4$$3$$2$$1$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$ Figure 9: Special MPCS of
Cayley tree

Table 2 lists three important parameters $n_{l},N_{1},N_{2}$ of Cayley trees.
From the last column of Table 2, we can see that $N_{2}$ decrease to 0
rapidly, to the extent that the probability of finding the optimal solution is
less than one in ten million after only 4 iterations.

Table 2: Minimum number of minimum sets of leaders of Cayley trees $g$ | $n$ | $n_{l}$ | $N_{1}$ | $N_{2}$
---|---|---|---|---
1 | 4 | 2 | $\frac{1}{2}$ | $\frac{1}{2}$
2 | 10 | 3 | $\frac{3}{10}$ | $\frac{1}{15}$
3 | 22 | 6 | $\frac{3}{11}$ | $8.5776\\!\\!\times\\!\\!10^{-4}$
4 | 46 | 12 | $\frac{6}{23}$ | $1.0527\\!\\!\times\\!\\!10^{-7}$
5 | 94 | 26 | $\frac{23}{47}$ | $2.2685\\!\\!\times\\!\\!10^{-14}$
$g\geq 6$ | $3\\!\cdot\\!2^{g}\\!\\!-\\!\\!2$ | $\frac{51}{64}\\!\cdot\\!2^{g}$ | $\frac{17}{64}\,(g\rightarrow\infty)$ | $0\,\,(g\rightarrow\infty)$
$g\\!\\!\neq\\!\\!5(mod4)$ |  |  |  |
$g\geq 6$ | $\quad 3\\!\cdot\\!2^{g}\\!\\!-\\!\\!2\quad$ | $\quad\frac{27}{32}\\!\cdot\\!2^{g}\quad$ | $\quad\frac{9}{32}\,(g\rightarrow\infty)$ | $0\,\,(g\rightarrow\infty)$
$g\\!\\!=\\!\\!5(mod4)$ |  |  |  |

##  5 Conclusion

The controllability of undirected graphs has attracted considerable attention
in recent years. However, the roles of leaders, the minimum number of leaders,
and the leader location in a undirected graph are yet to be fully understood.
A major contribution of this paper was to provide a method to determine the
leaders directly from the topology structures of undirected graphs. These
contributions can enhance our understanding of the leader’s role in the
controllability of undirected graphs. To this end, we introduced the concepts
of a critical set, perfect critical set, and minimal perfect critical set.
These concepts indicate that some vertices with special graphical
characterization should be selected as leaders. Necessary and sufficient
conditions were proposed to uncover some special minimal perfect critical set.
We described the graphical characterizations of minimal perfect critical 2
set. Further, we proved that minimal perfect critical 3 set does not exist. In
addition, we pointed out that every tree graph is controllable when the leader
set contains at least $|S_{0}|-1$ pendent vertices, where $S_{0}$ is the
pendent vertex set. Moreover, we studied an isolated vertex set and found that
if $S$ is isolated and $|S|\geq 3$, then $S$ is not an MPCS. Finally, we
completely described the MPCS of a tree graph with
$|N_{\tilde{G}}(v)\cap\bar{S}|\leq 1(\forall v\in S)$ and showed that it can
be used to discover some special MPCS of tree graphs.

All these results, which clearly indicate where the leaders are located,
reveal the effect of the topology structure on controllability, and they could
promote further investigation of the controllability of undirected graphs. To
determine the characteristics of MPCS in a general network is an important
topic that warrants in-depth analysis.

## References

  * [1] Tanner HG. On the controllability of nearest neighbor interconnections. 43rd IEEE Conference on Decision Control, December 2004, 14(17): 2467-2472.
  * [2] Meng J and Egerstedt M. A graph-theoretic characterization of controllability for multi-agent systems. Proceedings of the 2007 American Control Conference, Marriott Marquis Hotel at Times Square, New York City, USA, July 11-13, 2007: 4588-4593.
  * [3] Rahmani A and Mesbahi M. On the controlled agreement problem. Proceedings of the 2006 American Control Conference, Minneapolis, Minnesota, USA, Jun,14-16, 2006: 1376-1381.
  * [4] Ji Z J, Wang Z D, Lin H and Wang Z. Interconnection topologies for multi-agent coordination under leader-follower framework. Automatica. 2009, 45(12): 2857-2863.
  * [5] Wang L, Jiang FC, Xie GM and Ji ZJ. Controllability of multi-agent systems based on agreement protocols. Science in China. Series F: Information Sciences, 2009, 52(11): 2074-2088.
  * [6] Ji ZJ and Yu HS. A new perspective to graphical characterization of multiagent controllability. IEEE Transactions on Cybernetics, 2017, 47(6): 1471-1483
  * [7] Rahmani A, Ji M, Mesbahi M, et a1. Controllability of multi?agent systems from a graph?theoretic perspective. SIAM Journal on Control and Optimization, 48(1), 2009:162-186
  * [8] Martini S, Egerstedt M and Bicchi A. Controllability analysis of multi-agent systems using relaxed equitable partitions. International Journal of Systems, Control and Communications, 2(1/2/3), 2010:100-121
  * [9] Aguilar CO and Gharesifard B. On almost equitable partitions and network controllability. American Control Conference. IEEE, 2016
  * [10] Aguilar C O and Gharesifard B. Almost equitable partitions and new necessary conditions for network controllability. Automatica, 2017, 80:25?31
  * [11] Cesar OA and Bahman G. Almost equitable partitions and new necessary conditions for network controllability. Automatica, 2017, 80:25-31
  * [12] AIM Minimum Rank?Special Graphs Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, vol. 428, no. 7, 2008:1628-1648
  * [13] Liang H H, Gerard J and Chang H G. On minimum rank and zero forcing sets of a graph. Linear Algebra and its Applications, 432, 2010:2961-2973
  * [14] Daniel B, Domenico D A, Leslie H, et al. Zero forcing, linear and quantum controllability for systems evolving on networks. IEEE Transactions on Automatic Control, Vol.58, NO.9, September 2013:2349-2354
  * [15] Monshizadeh N, Zhang S and Camlibel MK. Zero forcing sets and controllability of dynamical systems defined on graphs. IEEE Trans. Automat. Control, vol. 59, no. 9, 2014:2562-2567
  * [16] Trefois M and Delvenne JC. Zero forcing number, constrained matchings and strong structural controllability. Linear Algebra Appl., vol.484, 2015:199-218
  * [17] Shima SM, Mohammad H and Mehran M. On the structural and strong structural controllability of undirected networks. IEEE Transactions on Automatic Control, 63(7), 2018: 2234-2241
  * [18] Kumar Y , Shana M , and Prasanna C . Minimizing inputs for strong structural controllability. 2019 American Control Conference (ACC), Philadelphia, PA, USA, July 10-12, 2019:2048-2053
  * [19] Olesky D, Tsatsomeros M and Driessche PVD. Qualitative controllability and uncontrollability by a single entry. Linear Algebra Appl., vol.187, 1993:183-194
  * [20] Airlie C and Mehran M . On strong structural controllability of networked systems: A constrained matching approach. 2013 American Control Conference (ACC) Washington, DC, USA, June 17-19, 2013:6126-6131
  * [21] Kalman RE. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics. Series A, 1(2), 1963:152-192
  * [22] Lin C. Structural controllability. IEEE Transactions on Automatic Control, AC-19(3), 1974:201-208
  * [23] Mayeda H and Yamada T. Strong structural controllability. SIAM Journal on Control and Optimization, Vol. 17, No. 1, 1979: 123-138
  * [24] Liu YG, Slotine JJ and Barabasi AL. Controllability of complex networks. Nature. 473(7346),2011:167-173
  * [25] Liu XZ and Ji ZJ. Controllability of multiagent systems based on path and cycle graphs. International Journal of Robust and Nonlinear Control. 28(1),2018:296-309
  * [26] Brockett RW. Finite dimensional linear systems. Wiley and Sons,1970
  * [27] Biyikoglu T, Leydold J and Stadler PF. Laplacian eigenvectors of graphs. Lecture Notes in Mathematics, Heidelberg, Germany, Springer, 2007
  * [28] Ji ZJ,Lin H,Lee T H,et al. Multi-agent controllability with tree topology. Proceedings of the 2010 American Control Conference. Baltimore, USA:IEEE,2010:850-855
  * [29] Ji ZJ,Lin H and Yu H. Leaders in multi-agent controllability under consensus algorithm and tree topology. System & Control Letters, 61(9), 2012:918-925
  * [30] Parlangeli G and Notarstefano G. Controllability and observability of grid graphs via reduction and symmetries. IEEE Transactions on Automatic Control,58(7),2013:1719-1731
  * [31] Nabiabdolyousefi M and Mesbahi M. On the controllability properties of circulant networks. IEEE Transactions on Automatic Control, 58(12),2013:3179-3184
  * [32] Barabasi A , Ravasz E and Vicsek T. Deterministic scale-free networks. Physica A 299, 2001:559-564
  * [33] Kazumoto I and Hiroaki Y . Exactly solvable scale-free network model. Physical Review E ,71, 2005:036144
  * [34] Yang-Yu L, Jean-Jacques S and Albert-Laszlo B. Controllability of complex networks. Nature, Vol.473, 2011:167-173
  * [35] Alafate J, Bin W and Zhongzhi Z . Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications. The Journal of Chemical Physics,138,2013:204116