arXiv:1608.02276v1  [cs.RO]  7 Aug 2016
Decentralized Biconnectivity Conditions in Multi-robot Systems
Mehran Zareh, Lorenzo Sabattini, and Cristian Secchi
Abstract— The network connectivity in a group of cooper-
ative robots can be easily broken if one of them loses its
connectivity with the rest of the group. In case of having
robustness with respect to one-robot-fail, the communication
network is termed biconnected. In simple words, to have a
biconnected network graph, we need to prove that there exists
no articulation point. We propose a decentralized approach that
provides sufficient conditions for biconnectivity of the network,
and we prove that these conditions are related to the third
smallest eigenvalue of the Laplacian matrix. Data exchange
among the robots is supposed to be neighbor-to-neighbor.
I. INTRODUCTION
The last decade has witnessed a growing interest in
decentralized control and decision making [1]–[3]. Recent
developments have made it possible to have a large group
of autonomous robots working cooperatively to perform
complex tasks which are simply not feasible by a single
robot. Since the global information is not always available,
control design for multi-robot systems based on local in-
formation exchange is a challenging task. Accordingly, the
design of control systems has shifted from centralized to
decentralized, where the information, locally collected by the
units (robots), is processed in locus and control decisions are
taken cooperatively by the robots with no supervision.
Usually, the robots move in unknown environments with
obstacles and they can get trapped. If the rest of the team
continues moving far from a trapped robot, the communi-
cation between that robot and the team becomes weaker
and finally the robot gets disconnected from the group.
Therefore, sensing the connectivity and trying to preserve it,
is a substantial task that must be seen as an objective of the
control action. There are two main approaches to preserve
the connectivity: the ones to maintain the local connectivity,
and approaches to preserve the global connectivity. In local
connectivity maintenance the aim is to develop a controller
that keeps all initially existing communication links. Some
examples of decentralized controller design for local connec-
tivity maintenance algorithms can be found in [4], [5]. Using
these approaches, a proof for the network connectivity can
be given. However, assuming the maintenance of every link
is too restrictive, and several researchers have considered
relaxations to the local connectivity maintenance such as
assuming a spanning tree [6], and k-hop connectivity [7].
In comparison to the local ones, the global connectivity
maintenance algorithms are based on global quantities of the
Authors
are
with
the
Department
of
Sciences
and
Methods
for
Engineering
(DISMI),
University
of
Modena
and
Reggio
Emilia,
Italy
{mehran.zareh, lorenzo.sabattini,
cristian.secchi}@unimore.it
network, and do not restrict link failures or creations (see
e.g. [8]–[11]). In [12], the authors propose a decentralized
algorithm and quantify the connectivity property of the multi-
agent system with the second smallest eigenvalue of the state
dependent Laplacian of the proximity graph. In [13], using
an additional locally generated and communicated variable,
a decentralized estimate of the Laplacian spectrum is pro-
vided. In [14], using a previously introduced decentralized
estimator, the Fiedler vector and the algebraic connectivity
are estimated.
In order to achieve a robust communication in a team
of cooperating mobile robots, the connectivity must be
preserved when a single robot crashes or is suddenly called
by a human user to perform another task. This is equivalent
to requiring that the network graph remains connected if
one of the nodes and all its incident edges are removed.
A graph with this property is said to be biconnected [15].
In addition to robustness, biconnectivity provides a better
bandwidth for communication by providing multiple paths
to the destination. The connectivity robustness of robot net-
works under failures is often neglected in the literature. Some
related works in graph theory describe algorithms to find
biconnected components in a graph based on optimization
theories. The algorithms mainly utilize depth-first search
or backtracking [16], [17] in a centralized way. In [18],
[19], the problem of biconnectivity check in a network is
addressed. Although the algorithm is labeled distributed,
the information exchange to make a table of connected
and doubly-connected nodes is assumed, which imposes the
nodes to exchange a big amount of information. In [20], an
algorithm to change a connected mobile robot graph into a
biconnected configuration is proposed. Since the algorithm
requires a global probe, it cannot be seen as a decentralized
one. Very recently, [21] investigated the robustness problem
in multi-robot systems so that, despite robot failures, most of
them remain connected and are able to continue the mission.
Based on a maximum 2-hop communication, each robot is
able to detect dangerous topological configurations in the
sense of the connectivity and can mitigate in order to reach
a new position to get a better connectivity level. The paper,
based on local information, introduces a parameter, called
vulnerability, that allows each robot to detect the level of its
effect on the topological configuration.
In this paper, we provide algorithms to enable each node
of the network graph to detect if it is a crucial one for
the network connectivity, i.e., a node whose disconnection
causes loss of connectivity of the graph. These nodes are
termed as articulation points. To the best of the authors’
knowledge, the problem of decentralized articulation point
detection has not been studied by now. First, each robot
perturbs its communication link weight. Then, based on
matrix perturbation theory, the condition for each robot not
to be an articulation point is achieved. Obviously, if there
is no articulation point, the resulting graph is biconnected.
We show that the graph biconnectivity is related to the third
smallest eigenvalue of the Laplacian matrix.
The rest of the paper is organized as follows. First, we
introduce notations and some basic theorems and definitions
on graph theory, which will be used in this work. Section III
introduces the main problem, and provides some essential
definitions. Section IV provides the main contribution of
this paper. We provide some theorems on perturbed commu-
nication weights to detect the articulation points with only
1-hop communications. In Section V the simulation results
are given to verify the theoretical findings. Finally, Section
VI concludes the paper, describes the open problems, and
outlines the future directions.
II. PRELIMINARIES
In this section we recall some basic notions and definitions
on graph theory and we introduce the notation used in the
paper.
The topology of bidirectional communication channels
among the robots is represented by an undirected graph
G = (V, E) where V = {1, . . ., n} is the set of nodes (robots)
and E ⊂V × V is the set of edges. An edge (i, j) ∈E
exists if there is a communication channel between robots
i and j. Self loops (i, i) are not considered. The set of
robot i’s neighbors is denoted by Ni = {j
:
(j, i) ∈
E; j = 1, . . . , n}. The network graph G is encoded by the
so-called adjacency matrix, an n × n matrix A whose (i, j)-
th entry aij is greater than 0 if (i, j) ∈E, 0 otherwise.
Obviously in an undirected graph matrix A is symmetric.
The degree matrix is defined as D = diag(d1, d2, . . . , dn)
where di = Pn
j=1 aij is the degree of node i. The Laplacian
matrix of a graph is defined as
= D −A. The Laplacian
matrix of a graph has several structural properties. It has
non-negative real eigenvalues for any graph G. Furthermore,
let 1 and 0 be respectively the vectors of ones and zeros
with proper dimensions, then 1 = 0 and 1T = 0T . Denote
by λi(·) the i-th leftmost eigenvalue, and by vi(·) and wi(·)
the right and left eigenvectors associated with λi(·). In this
way, the eigenvalues of the Laplacian matrix can be ordered
as
0 = λ1() ≤λ2() ≤. . . ≤λn().
In G a node i is reachable from a node j if there exists an
undirected path from j to i. If G is connected then is a sym-
metric positive semidefinite irreducible matrix. Moreover, the
algebraic multiplicity of the null eigenvalue of is one. For
a graph G, the second smallest eigenvalue of the Laplacian
matrix is called algebraic connectivity. This eigenvalue gives
a qualitative measure of connectedness of the graph. Al-
gebraic connectivity is a non-decreasing function of graphs
with the same set of vertices. This means that, if G1(V, E1)
and G2(V, E2) are two graphs constructed on the set V such
that E1 ⊆E2, then λ2(1) ≤λ2(2). In the other words, the
more connected the graph becomes the larger the algebraic
connectivity will be. The corresponding eigenvector to the
second smallest eigenvalue is called Fiedler vector, which
gives very useful information about the graph [22]. The next
lemma explains a relation between the eigenvectors of a
Laplacian matrix.
Lemma 1
[23] Let vk(), 1 < k ≤n, be a non-null
eigenvector of the Laplacian matrix. Then
vT
k ()1 = 0.
(1)
We denote ˜ai = [aij]T ∈Rn−1,
j = 1, . . . , n, j ̸= i. We
also define the perturbed adjacency matrix Ai(ǫ) obtained
from A by multiplying all aij and ajis by ǫ ∈R+. The asso-
ciated perturbed degree Di(ǫ) = diag(Ai(ǫ)1) and Laplacian
matrix i(ǫ) = Di(ǫ) −Ai(ǫ) are defined accordingly. We
indicate the reduced graph GRi achieved from G by removing
node i and all its incident edges. Accordingly, ARi is the
adjacency matrix, DRi is the degree matrix, and Ri is the
Laplacian matrix of GRi.
Communications are assumed to be between each robot
and its 1-hop neighbors. We assume that the network con-
nectivity is guaranteed, and each robot can properly estimate
the algebraic connectivity. For the connectivity maintenance
conditions and algebraic connectivity estimation procedure,
the readers are referred to [9], [13], [14].
III. PROBLEM STATEMENT
Consider a network of n(> 2) robots whose interconnec-
tion structure is modeled by an undirected graph G(V, E).
The following definitions from the algebraic graph theory
will be used in the rest of this paper.
Definition 1 A vertex i ∈V of a connected graph G is called
an articulation point if GRi is not connected.
Definition 2 A connected graph is called biconnected if it
has no articulation point.
Definition 3 A block in G is a maximal induced connected
subgraph with no articulation point. If G itself is connected
and has no articulation point, then G is a block [24].
Definition 4 In a graph G(V, E), two paths between vertices
i, j ∈V are called internally disjoint if they have no other
vertices in common.
Definition 5 In a graph G(V, E), two vertices i, j ∈V are
said to be doubly connected ⇐⇒there are two or more
internally disjoint paths between them.
The following lemma, from [19], explains the relation be-
tween biconnectivity and doubly connected vertices.
Lemma 2 A given undirected graph G(V, E) is biconnected
⇐⇒any two vertices i, j ∈V are doubly connected.
Now we are ready to define the main problem that we are
going to study in this paper.
Problem 1 For a multi-robot system with a connected in-
teraction graph G, find conditions based only on local data
exchange so that there are more than one internally disjoint
paths between any pair of nodes. Equivalently, from Lemma
2, we are looking for the conditions under which the graph
is biconnected.
A very quick question that comes after the above problem
is that if the graph is not biconnected, what strategies can
bring the graph to the desired configuration. We leave this
problem for future studies.
IV. MAIN CONTRIBUTION
To enable each single robot to be aware of its connectivity
status in the graph, it needs to know the characteristics of the
network graph when all its incident edges are disconnected.
If the graph remains connected when the robot i fails, then
the node i in the graph is not an articulation point. By putting
weakly connected links between node i and its neighbors,
we aim at providing an estimate of the conditions after a
complete disconnection. The proposed methodology includes
the following steps
a) First, we introduce an intermediate matrix P i(ǫ), for each
node i, whose eigenvalues are equal to the non-null ones
of the perturbed Laplacian matrix i(ǫ) with ǫ ∈R+ as a
local design parameter (Theorem 1).
b) Then, we find an upper bound on the maximum gap
between the pairs of the eigenvalues of this intermediate
matrix and those of the reduced Laplacian matrix, Ri
(Proposition 1 and Lemma 3).
c) We provide some conditions on the third smallest eigen-
value of the perturbed Laplacian matrix so that the
reduced graph GRi remains connected (Theorem 2).
d) Finally, we demonstrate that, if the above conditions hold
only for non-locally biconnected (defined later) nodes of
G, then G is biconnected (Proposition 2 and Corollary 2).
Theorem 1 Given an undirected graph G(V, E) with n
nodes, for a given real scalar ǫ, the eigenvalues of the
following matrix
P i(ǫ) = Ri + ǫdiag(˜aT
i ) + ǫ˜ai1T ,
(2)
are equal to non-null eigenvalues of i(ǫ).
Proof: Without loss of generality, assume that the node
i is the last node, that is, the associated elements in the
adjacency, degree, and Laplacian matrices are in the last
column and row. We can simply reformulate the perturbed
adjacency matrix as
Ai(ǫ) =

ARi
ǫ˜ai
ǫ˜aT
i
0

,
(3)
and, subsequently, the perturbed degree matrices as
Di(ǫ) = diag(Ai(ǫ)1) =
 DRi + ǫdiag(˜aT
i )
0
0T
ǫdi

. (4)
By simple calculations we get
i(ǫ) = Di(ǫ) −Ai(ǫ) =
 Ri + ǫdiag(˜aT
i )
−ǫ˜ai
−ǫ˜aT
i
ǫdi

. (5)
Let λi(i(ǫ)) be a non-null eigenvalue of i(ǫ) and v(i(ǫ)) =
 v1(i(ǫ))
v2(i(ǫ))

, with v1(i(ǫ)) ∈Rn−1, and v2(i(ǫ)) ∈R, be a
corresponding eigenvector. We have
i(ǫ)v(i(ǫ)) = λ(i(ǫ))v(i(ǫ)).
(6)
or













(Ri + ǫdiag(˜aT
i ))v1(i(ǫ)) −ǫ˜aiv2(i(ǫ)) =
λ(i(ǫ))v1(i(ǫ))
−ǫ˜aT
i v1(i(ǫ)) + ǫdiv2(i(ǫ)) =
λ(i(ǫ))v2(i(ǫ)).
(7)
From Lemma 1 we can find a relationship between v1(i(ǫ))
and v2(i(ǫ)). We know that
vT (i(ǫ))1 = 0,
hence
v2(i(ǫ)) = −v1T (i(ǫ))1 = −1T v1(i(ǫ)).
(8)
By replacing in the first equation of (??), we obtain
(Ri + ǫdiag(˜aT
i ) + ǫ˜ai1T )v1(i(ǫ)) = λi(i(ǫ))v1(i(ǫ)), (9)
which proves that λ(i(ǫ)) is an eigenvalue of the matrix
P i(ǫ) = (Ri + ǫdiag(˜aT
i ) + ǫ˜ai1), and the corresponding
eigenvector is v1(i(ǫ)).
Corollary 1 If G is a connected graph, then i(ǫ) has only
one null eigenvalue and the other eigenvalues are positive.
Then
λk(P i(ǫ)) = λk+1(i(ǫ)) for k = 1, . . . , n −1.
Note P i(ǫ) is achieved from Ri perturbed by the non-
symmetric term ǫ(diag(˜ai) + ˜ai1T ). Before introducing a
theorem to find an upper bound on the eigenvalue changes
between these matrices, we need to show that any linear
combination of them gets real eigenvalues.
Proposition 1 For any given α, β ∈R and ǫ ∈R so that
α2 + β2 ̸= 0, the linear combination F i(ǫ) = αRi + βP i(ǫ)
has real eigenvalues.
Proof: See the Appendix.
To ensure the connectivity of the network graph after
a possible failure of a node, we need to estimate the
algebraic connectivity of the reduced graph. Obviously, if
the second-smallest eigenvalue of the reduced Laplacian
matrix is positive, then the reduced graph is connected.
The next lemma introduces an important result from matrix
perturbation theory, which enables us to find an upper bound
on the distance between the pairs of the eigenvalues of two
non-symmetrically perturbed matrices.
Lemma 3
[25] Let A be an n × n matrix with eigenvalues
ψ1 ≥. . . ≥ψn and B an n × n matrix with eigenvalues
ξ1 ≥. . . . . . ≥ξn. Define the gap between the eigenvalues
of these matrices as
gap(A, B) = max
j
|ψj −ξj|.
(10)
If all the real linear combinations of A and B have only real
eigenvalues, then
gap(A, B) ≤∥A −B∥,
(11)
where ∥· ∥indicates the Euclidean norm.
Now we are ready to introduce the main result of this
paper. The next theorem provides some sufficient conditions
for biconnectivity of a network based on finding a bound on
the algebraic connectivity of reduced graphs.
Theorem 2 For a given multi-robot system with n robots
(n > 2), whose interaction network graph is modeled by an
undirected connected graph G(V, E), the node i is not an
articulation point if, for a small ǫ ∈R+, we have
λ3(i(ǫ)) > ǫ√n (
n
X
k=1
a2
ik)1/2.
(12)
Proof: Notice that, if node i is not an articulation point,
then the reduced graph GRi is a connected graph, and hence
Ri has a positive second-smallest eigenvalue. Proposition 1
shows that any linear combination of Ri and P i(ǫ) has real
eigenvalues. Therefore, due to Lemma 3, the gap between
the eigenvalues of P i(ǫ) and R
i is bounded by
gap(P i(ǫ), R
i ) ≤∥P i(ǫ) −Ri∥= ǫ∥diag(˜ai) + ˜ai1T ∥.
It can be trivially shown that
diag(˜ai) + ˜ai1T =


a11
. . .
a11
...
...
an−1,n−1
. . .
an−1,n−1

.
The Euclidean norm of a matrix is the square root of the
sum of the squares of its elements. Hence
∥diag(˜ai) + ˜ai1T ∥= √n (
n
X
k=1
a2
ik)1/2.
From (??) and (??), we have
∥λ2(P i(ǫ)) −λ2(LRi)∥≤ǫ√n (
n
X
k=1
a2
ik)1/2.
To prove the connectivity of GRi we need to show that
λ2(Ri) > 0 or
λ2(P i(ǫ)) > ǫ√n(
n
X
k=1
a2
ik)1/2.
Since the graph is connected, from Remark 1 we get
λ2(P i(ǫ)) = λ3(i(ǫ)) > ǫ√n(
n
X
k=1
a2
ik)1/2.
This means that, if we remove node i from the network, it
remains connected. In other words, if the condition (??) is
true, then node i is not an articulation point.
Using Theorem 2 for all the nodes, if a decentralized
eigenvalue estimation like the approach introduced in [13]
is implemented, then we only need local data to check the
biconnectivity. However, in many multi-robot schemes, as
formation control and rendezvous problems, the robots have
some assigned tasks, and biconnectivity check introduces an
extra effort to the robots that can lead to a loss in time and
energy. On the other hand, when the biconnectivity check
is necessary, an additional amount of energy or time loss
is admitted. Therefore, if some of the robots can somehow
sense that they are not in the risk of being an articulation
point, they can skip the biconnectivity check. The next
proposition can help each node to be aware of its own
connectivity status to avoid unnecessary checks.
Proposition 2 In a connected graph G(V, E), node i is not
an articulation point if the subgraph created on the set {i}∪
Ni forms a block.
Proof: Define V1 = {i} ∪Ni and V2 = V/V1. Assume
that the subgraph based on V1, namely G(V1) is a block. Due
to the connectivity of the graph, there exists at least one path
that connects each node in V2 to the block G(V1). Notice that
there is no node in V2 adjacent to i otherwise it would be in
Ni. Since the subgraph G(V1) is a block, we can conclude
that the subgraph G(V1/i) is connected. Consequently, the
subgraph G((V1 ∪V2 = V)/i) is connected. Therefore, from
the definition, node i is not an articulation point.
A node that satisfies Proposition 2, is called locally bicon-
nected.
Remark 1 In an undirected communication network graph,
to characterize the local subgraph, each node only needs to
receive the positions of its neighbors. Then, based on this
model, the local adjacency, degree, and Laplacian matrices
can be determined. If the second smallest eigenvalue of
the Laplacian matrix is positive then that node is locally
biconnected.
Now we can summarize our theorems by the following
corollary.
Corollary 2 A connected graph G(V, E) is biconnected if
every node of G that is not locally biconnected meets the
condition in (??).
V. SIMULATION RESULTS
In this section we present simulation results to verify the
theoretical analysis.
Example 1 We suppose that the communications are defined
by the R-disk model, in which the elements of the adjacency
matrix are defined as
aij =

e−(∥pi−pj∥2)/(2σ)
∥pi −pj∥≤R
0
∥pi −pj∥> R,
where pi indicated the position of robot i. For this simulation,
we selected R = 0.5 and σ = 0.125. Consider the randomly
generated network with n = 10 in Figure 1. We can see
that the only node that is not locally biconnected (see
Figure 2), is the one denoted by ∗. Hence, based on the
proposed algorithm, this node starts doing a biconnectivity
check. Selecting ǫ = 0.05 gives λ3(∗(ǫ)) = 0.034, and
Node *
Fig. 1.
Communication graph in Example 1.
Node *
Fig. 2.
Local graph associated to node ∗in Example 1
(Pn
k=1 a2
∗k)1/2 = 0.062. We can verify that the conditions
in (??) holds
λ3(∗(ǫ)) = 0.034 > 0.05 ×
√
10 × 0.062 = 0.0098.
As we expected, the node ∗meets the sufficient conditions to
for not being an articulation point.
Notice that the condition in (??) is not necessary but suffi-
cient. This means that, if we keep the same graph and we
change the weights, (??) might not hold anymore.
VI. CONCLUSIONS AND FUTURE WORKS
In this manuscript, a decentralized algorithm to determine
the sufficient conditions for analyzing biconnectivity was
introduced. The definition of locally biconnected node was
presented. We proved that, in order to have a biconnected
network, the nodes that are not locally biconnected must
meet a special condition, one the third-smallest eigenvalue of
the Laplacian matrix. This condition was obtained by making
the nodes close to the disconnection. We also presented
some theorems on the eigenvalues of non-symmetrically
perturbed Laplacian matrix, and we used them to achieve
the biconnectivity condition for the algorithm. In our future
work, we are going to develop a decentralized protocol to
obtain a biconnected network graph.
APPENDIX
In this section we provide the proof of Proposition 1. For
this purpose, we need some preliminary manipulations and
lemmas. Let γ = α + β and η = βǫ. From (??) we get
F i(ǫ) =
(α + β)Ri + βǫ(diag(˜aT
i ) + ˜ai1T
n−1)
=
γRi + η(diag(˜aT
i ) + ˜a1T ).
For β = 0, F i(ǫ) becomes a symmetric matrix, and one can
trivially show that it has real eigenvalues. So we need to
prove the proposition for β ̸= 0. Let Qi(η) = γRi + η˜ai1.
This gives
F i(ǫ = η/β) = Qi(η) + ηdiag(˜aT
i ).
(13)
For convenience, hereafter we denote F i(η/β) by F i(η).
We recall the following lemma from the perturbation
theory.
Lemma 4 [26] For a non-negative real number η, consider
a matrix M(η) and let λ1(M) = . . . = λk(M), k ∈
[1, n] be a semi-simple eigenvalue1 of M(0). Denote by
v1(M), . . . , vl(M) and w1(M), . . . , wl(M) associated right
and left eigenvectors such that


wT
1 (M)
. . .
wT
l (M)


v1(M)
. . .
vl(M)

= I.
Let M ′ = dM(η)
dη
|η=0. Then the derivatives of the eigenvalues
of M with respect to η, dλ(M)
dη
|η=0, exist, and they are the
eigenvalues of the following matrix
∆=


w1(M)T M ′v1(M)
. . .
w1(M)T M ′vl(M)
...
...
...
wl(M)T M ′v1(M)
. . .
wl(M)T M ′vl(M)


(14)
In order to prove Proposition 1, we introduce the following
steps:
a) In the first step, we characterize the eigenvalues of Qi(η),
and we show they are all real.
b) The second step is to demonstrate that the eigenvalues of
F i(η) are all real.
Eigenvalues of Qi(η)
Note that Qi(η) is obtained by perturbing matrix γRi by
η˜ai1T .
Lemma 5 Let G be a connected graph and
Ri be the
Laplacian matrix of GRi, with l null eigenvalues λ1(Ri) =
λ2(Ri) = . . . = λl(Ri) = 0. Then for the k-th eigenvalue of
Qi we get
λk(Qi) = γλk(Ri),
k = l + 1, . . . , n −1,
(15)
while for a small η ∈R
1 An eigenvalue of a matrix is called semi-simple if its algebraic
multiplicity is equal to its geometric multiplicity.
λk(Qi) = 0,
k = 2, . . . , l,
(16)
and λ1(Qi)(η) gets a positive value.
Proof: For non-null eigenvalues of the reduced Lapla-
cian matrix we have
vT
k (Ri)1 = 1T vk(Ri) = 0,
k = l + 1, . . . , n −1.
Multiply Qi and vk(Ri)
Qi(η)vk(Ri) = γR
i vk(Ri) + η˜ai1T vk(Ri)
= γλk(Ri)vk(Ri), k = l + 1, . . . , n −1.
which shows that all the non-null eigenvalues of Qi(η) are
equal to those of γRi.
The null eigenvalue of a Laplacian matrix is semi-simple
[27]. Let {v1(Ri), . . . , vl(Ri)} be a set of orthogonal eigen-
vectors associated with the null eigenvalue of Ri. Without
loosing generality, let v1(Ri) = 1. Since Qi(0) = γRi is
symmetric, the left eigenvectors are equal to the right ones.
Replacing M ′ = dQi(η)/dη = ˜ai1, w1(M) = v1(M) = 1,
wk(M) = vk(M) = vk(Ri), k = 2, . . . , l in (??), knowing
that 1T vj(Ri) = 0, j = 2, . . . , l, we get
∆1,1 = wT
1 M ′v1 = 1T (diag(˜aT
i )1T )1 = (n −1)
n
X
k=1
aik
∆m,j = wT
mM ′vj = wT
m(diag(˜aT
i )1T )vj = 0
m, j = 1, . . . , l,
(m, j) ̸= (1, 1)
.
(17)
Since the graph is supposed to be connected, then ˜ai ̸= 0 ∀i.
Hence the matrix in (??) has only one non-null eigenvalue
equal to (n −1) Pn
k=1 aik. Consequently
dλk(Qi)
dη
|η=0 =





(n −1)
n
X
k=1
aik > 0
k = 1
0
k = 2, . . . , l
(18)
This means that, by changing η from zero, all the null
eigenvalues of Qi(η) remain on the origin apart from one
that moves to the right along the real axis.
So we proved that all the eigenvalues of Qi(η), and con-
sequently the associated eigenvectors, get only real values.
Eigenvalues of F i(η)
Now we want to show that the eigenvalues of F i(η) are
all real and cannot get complex values.
Proof:
Let λ(F i) be an eigenvalue of F i(η) and v(F i) be an
associated eigenvector, that both can possibly get complex
values.
F i(η)v(F i) = λ(F i)v(F i).
(19)
For a small η we can write
λ(F i) =
∞
X
k=0
λk(F i)ηk,
(20)
and
v(F i) =
∞
X
k=0
vk(F i)ηk.
(21)
where λk(F i) and vk(F i) may also take complex values. We
use induction to prove that all the eigenvalues of F i(η) are
real. In this way, we first show that the statement is true for
the first element (λ0(F i) is real). Afterwards, we show that
all the first k −1 elements are real, then the k-th eigenvalue
is also real.
From (??), (??), (??), and (??), we get
(Qi(η) + ηdiag(˜aT
i ))
∞
P
k=0
vk(F i)ηk =
∞
P
k=0
vk(F i)ηk
∞
P
k=0
λk(F i)ηk.
(22)
To verify the equality for a non-zero η, the coefficients of all
the exponents of η must be equal in both the left and right
side. For k = 0 we get
Qi(η)v0(F i) = λ0(F i)v0(F i),
This means that λ0(F i) is an eigenvalue of Qi(η) with the
associated left and right eigenvectors v0(F i), w0(F i), and
hence they are real. For k > 0, the equality of the two sides
gives
Qi(η)vk(F i) + diag(˜aT
i )vk−1(F i) =
k
X
l=0
λl(F i)vk−l(F i).
By extracting the terms 0, 1, and k from the sum and doing
some manipulations, we reach to
(Qi(η) −λ0(F i)I)vk(F i)
+(diag(˜aT
i ) −λ1(F i)I)vk−1(F i)
−
k−1
P
l=2
λl(F i)vk−l(F i) = λk(F i)v0(F i).
(23)
Now let w0(F i) be a left eigenvector of F i(η) for λ0(F i)
so that wT
0 (F i)v0(F i) = 1. Then we have
w0(F i)T (Qi(η) −λ0(F i)I) = 0.
By multiplying both sides of (??) by wT
0 (F i), the first term
in the left side becomes zero, and we get
wT
0 (F i)(diag(˜aT
i ) −λ1(F i)I)vk−1(F i)
−w0(F i)T
k−1
P
l=2
λl(F i)vk−l(F i)
= λk(F i)wT
0 (F i)v0(F i) = λk(F i).
(24)
Notice that, if λl(F i) are real for l = 0, . . . , k −1 , then
vl(F i) become all real valued. This implies that the left
hand side of (??) is a real number and consequently λk(F i)
must get a real value. Therefore, we prove the proposition
by induction.
REFERENCES
[1] R. Olfati-Saber and J. S. Shamma, “Consensus filters for sensor
networks and distributed sensor fusion,” in Decision and Control, 2005
and 2005 European Control Conference. CDC-ECC’05. 44th IEEE
Conference on.
IEEE, 2005, pp. 6698–6703.
[2] M. Zareh, C. Seatzu, and M. Franceschelli, “Consensus of second-
order multi-agent systems with time delays and slow switching topol-
ogy,” in Networking, Sensing and Control (ICNSC), 2013 10th IEEE
International Conference on, 2013, pp. 269–275.
[3] M. Zareh, “Consensus in multi-agent systems with time-delays,” Ph.D.
dissertation, University of Cagliari, May 2015.
[4] G. Notarstefano, K. Savla, F. Bullo, and A. Jadbabaie, “Maintaining
limited-range connectivity among second-order agents,” in American
Control Conference, 2006.
IEEE, 2006, pp. 6–pp.
[5] A. Ajorlou, A. Momeni, and A. G. Aghdam, “A class of bounded
distributed control strategies for connectivity preservation in multi-
agent systems,” Automatic Control, IEEE Transactions on, vol. 55,
no. 12, pp. 2828–2833, 2010.
[6] M. Schuresko and J. Cortés, “Distributed motion constraints for
algebraic connectivity of robotic networks,” Journal of Intelligent and
Robotic Systems, vol. 56, no. 1-2, pp. 99–126, 2009.
[7] M. M. Zavlanos and G. J. Pappas, “Distributed connectivity control
of mobile networks,” Robotics, IEEE Transactions on, vol. 24, no. 6,
pp. 1416–1428, 2008.
[8] M. M. Zavlanos, M. B. Egerstedt, and G. J. Pappas, “Graph-theoretic
connectivity control of mobile robot networks,” Proceedings of the
IEEE, vol. 99, no. 9, pp. 1525–1540, 2011.
[9] L. Sabattini, N. Chopra, and C. Secchi, “Decentralized connectivity
maintenance for cooperative control of mobile robotic systems,” The
International Journal of Robotics Research, vol. 32, no. 12, pp. 1411–
1423, 2013.
[10] L. Sabattini, C. Secchi, N. Chopra, and A. Gasparri, “Distributed
control of multirobot systems with global connectivity maintenance,”
Robotics, IEEE Transactions on, vol. 29, no. 5, pp. 1326–1332, 2013.
[11] P. Robuffo Giordano, A. Franchi, C. Secchi, and H. H. Bülthoff,
“A passivity-based decentralized strategy for generalized connectivity
maintenance,” The International Journal of Robotics Research, vol. 32,
no. 3, pp. 299–323, 2013.
[12] M. C. De Gennaro and A. Jadbabaie, “Decentralized control of
connectivity for multi-agent systems,” in Decision and Control, 2006
45th IEEE Conference on.
IEEE, 2006, pp. 3628–3633.
[13] M. Franceschelli, A. Gasparri, A. Giua, and C. Seatzu, “Decentralized
estimation of laplacian eigenvalues in multi-agent systems,” Automat-
ica, vol. 49, no. 4, pp. 1031–1036, 2013.
[14] P. Yang, R. A. Freeman, G. J. Gordon, K. M. Lynch, S. S. Srinivasa,
and R. Sukthankar, “Decentralized estimation and control of graph
connectivity for mobile sensor networks,” Automatica, vol. 46, no. 2,
pp. 390–396, 2010.
[15] M. C. Golumbic, Algorithmic graph theory and perfect graphs.
Elsevier, 2004, vol. 57.
[16] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM
journal on computing, vol. 1, no. 2, pp. 146–160, 1972.
[17] R. E. Tarjan and U. Vishkin, “Finding biconnected componemts and
computing tree functions in logarithmic parallel time,” in Foundations
of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984,
pp. 12–20.
[18] M. Ahmadi and P. Stone, “A distributed biconnectivity check,” in
Distributed Autonomous Robotic Systems 7. Springer, 2006, pp. 1–10.
[19] ——, “Keeping in touch: Maintaining biconnected structure by ho-
mogeneous robots,” in Proceedings of the National Conference on
Artificial Intelligence, vol. 21, no. 1.
Menlo Park, CA; Cambridge,
MA; London; AAAI Press; MIT Press; 1999, 2006, p. 580.
[20] J. Butterfield, K. Dantu, B. Gerkey, O. C. Jenkins, and G. S. Sukhatme,
“Autonomous biconnected networks of mobile robots,” in Modeling
and Optimization in Mobile, Ad Hoc, and Wireless Networks and
Workshops, 2008. WiOPT 2008. 6th International Symposium on.
IEEE, 2008, pp. 640–646.
[21] C. Ghedini, C. Secchi, C. H. C. Ribeiro, and L. Sabattini, “Improving
robustness in multi-robot networks,” in IFAC Symposium on Robot
Control (SYROCO).
IFAC, 2015.
[22] M. Fiedler, “A property of eigenvectors of nonnegative symmetric ma-
trices and its application to graph theory,” Czechoslovak Mathematical
Journal, vol. 25, no. 4, pp. 619–633, 1975.
[23] N. M. M. de Abreu, “Old and new results on algebraic connectivity
of graphs,” Linear algebra and its applications, vol. 423, no. 1, pp.
53–73, 2007.
[24] D. B. West, Introduction to graph theory.
Prentice hall Upper Saddle
River, 2001, vol. 2.
[25] R. Bhatia, Perturbation bounds for matrix eigenvalues.
SIAM, 1987,
vol. 53.
[26] A. P. Seyranian and A. A. Mailybaev, Multiparameter stability theory
with mechanical applications.
World Scientific, 2003, vol. 13.
[27] R. B. Bapat and S. Pati, “Algebraic connectivity and the characteristic
set of a graph,” Linear and Multilinear Algebra, vol. 45, no. 2-3, pp.
247–273, 1998.