2011 International Symposium on Nonlinear Theory and its Applications
NOLTA2011, Kobe, Japan, September 4-7, 2011

On Topology of Networked Multi-Agent Systems for Fast Consensus
Kohnosuke Ogiwara† and Norikazu Takahashi‡†Graduate School of Information Science and Electrical Engineering, Kyushu University
Motooka 744, Nishi-ku, Fukuoka, 819–0395 Japan‡Faculty of Information Science and Electrical Engineering, Kyushu University
Motooka 744, Nishi-ku, Fukuoka, 819–0395 Japan
Email: ogiwara@kairo.csce.kyushu-u.ac.jp, norikazu@inf.kyushu-u.ac.jp
Abstract—The rate of convergence of a consensus algorithm for networked multi-agent systems is determinedby the second smallest eigenvalue of the graph Laplacian.
In this paper, we consider the problem of finding undirected graphs maximizing the second smallest eigenvalueof the Laplacian for the given number of nodes and edges.
We show that under certain conditions the second smallest
eigenvalue of the Laplacian is maximized for some wellknown classes of graphs such as the cycle graph, the stargraph and the complete bipartite graph.
1. Introduction
A multi-agent system is a system composed of many
agents cooperating with each other to solve a certain problem. In recent years, the consensus problem for multi-agent
systems has attracted considerable attention from the engineering community [1, 2]. We say that a consensus isreached when the states of all agents converge to the samevalue, e.g., the average of the initial states. Consensus
problem is thus closely related to synchronization of coupled oscillators, flocking theory and distributed sensor fusion in sensor networks [1].
Olfati-Saber and Murray [2] proposed a consensus algorithm for multi-agent systems in which the time derivativeof the state of each agent is determined by the states ofother agents that can interact with it. They proved undercertain mild assumptions that the system reaches the average consensus for any initial state. They also showed thatthe speed of convergence of the system is proportional to
the second smallest eigenvalue of the graph Laplacian.
In this paper, we consider the problem of finding agraph that maximizes the second smallest eigenvalue of the
Laplacian among all graphs with the prescribed number ofnodes and edges. This is a fundamental problem closely related to the consensus algorithm proposed by Olfati-Saberand Murray [2]. First we focus our attention on graphs
composed of 5 or 6 nodes and find a graph maximizing
the second smallest eigenvalue of the Laplacian. Next weprove that 1) the cycle graph maximizes the second smallest eigenvalue when n = m ≤ 6 where n and m are the number of nodes and edges, respectively, 2) a graph obtainedby adding an edge to the star graph maximizes the second
smallest eigenvalue when n = m ≥ 6, 3) the cycle graphlocally maximizes the second smallest eigenvalue for any
n ≥ 3, 4) the complete bipartite graph Ka,n−a maximizes
the second smallest eigenvalue when a − 2a2 /n < 1 and 5)
the complete bipartite graph locally maximizes the second
smallest eigenvalue.
2. Consensus Algorithm
In a multi-agent system, each agent interacts with all orpart of other agents and thus these interactions are often
represented by a graph of which each node corresponds toan agent. Throughout this paper, we assume that interactions between agents are time-invariant and symmetric1 forsimplicity. Under this assumption, the interaction topology of a multi-agent system can be represented by a simple undirected graph G = (V, E) where V = {1, 2 . . . , n} isthe set of nodes and E is the set of edges, that is, the setof unordered pairs of two diﬀerent nodes. A pair {i, j} isa member of E if and only if there is interaction between
agents i and j.
Let A = (ai, j ) ∈ {0, 1}n×n be the adjacency matrix ofa simple undirected graph G = (V, E). Note that A is asymmetric matrix. Let D = diag(d1 , . . . , dn ) be the degree∑
matrix of G with elements di = j,i ai j for i = 1, 2, . . . , n.
Then the graph Laplacian of G is defined by
L = D − A.

(1)

By the definition of the graph Laplacian, it is apparent that
L1 = 0 = 0 · 1 holds where 1 is an n-dimensional column
vector of ones. This means that 0 is an eigenvalue of L
and its associated eigenvector is 1. Also, it is easily seenfrom Gershgorin’s theorem that all eigenvalues of L is nonnegative. From these facts, we can immediately conclude
that the smallest eigenvalue of L is always 0. On the other
hand, it is well known that the second smallest eigenvalueof L is nonzero if and only if G is connected.
Consensus algorithm proposed by Olfati-Saber and Murray [1] is described by the set of diﬀerential equations:- 56 -ẋi (t) =n∑ai j (x j (t) − xi (t)),

i = 1, 2, . . . , n

(2)

j=1
1 It is of course possible to consider nonsymmetric interactions [1, 2].

where xi (t) is the state of agent i at time t, ẋi (t) is the time
derivative of xi (t), and ai, j is the (i, j) entry of the adjacency
matrix A of the graph G for the multi-agent system. By
using the Laplacian L of G, Eq.(2) can be rewritten asẋ(t) = −Lx(t)(3)

where x(t) = (x1 (t), x2 (t), . . . , xn (t))T . The consensus algorithm (3) reaches an average-consensus if the corresponding graph G is connected [1]. More strictly speaking, xi (t)∑asymptotically converges to the average nj=1 x j (0)/n of n
initial states for all i. In addition, the speed of convergenceis proportional to the second smallest eigenvalue of L. In
algebraic graph theory, the second smallest eigenvalue ofthe graph Laplacian is called the algebraic connectivity [3].
Therefore, we hereafter use this terminology.
The algebraic connectivity of graphs considerably diﬀer
by their topology even though the number of nodes andedges are the same. For example, the speed of convergenceof the algorithm (2) for a system represented by the stargraph is ten times faster than that by the path graph.
3. Undirected Graphs Maximizing the Algebraic Connectivity

algebraic connectivity of those graphs are shown. Similarly, results for n = 6 are summarized in Fig. 2. Note thattwo graphs are presented in Figs. 1 (d), 2 (b) and 2 (g).
This means that algebraic connectivity maximizing graphin Gn,m is not uniquely determined in general.
3.3. Trees
Let δ(G) be the minimum degree of a graph G. Then thefollowing lemma holds.
Lemma 1 ([3]) If G is not a complete graph then λ2 (G) ≤δ(G).
If G is a tree, that is, the number of edges is less than thatof nodes by one, then δ(G) = 1. By Lemma 1, we have
λ2 (G) ≤ 1.

The graph with E = {{1, 2}, {1, 3}, . . . , {1, n}} is called thestar graph and denoted by S n . Concerning eigenvalues of
the Laplacian of S n , the following result is known.
Lemma 2 ([4]) Eigenvalues of the Laplacian of the stargraph S n are given by


0,



1,
λi (S n ) = 


 n,

3.1. Problem Formulation
Let Gn,m be the set of simple undirected graphs composed of n nodes and m edges. Let λ1 (G), λ2 (G), . . . , λn (G)be n eigenvalues of the Laplacian of G ∈ Gn,m . We assume
without loss of generality that eigenvalues are sorted in ascending order as 0 = λ1 (G) ≤ λ2 (G) ≤ . . . ≤ λn (G). Thenλ2 (G) is the algebraic connectivity of G.
Definition 1 A graph G ∈ Gn,m is said to be an algebraic
connectivity maximizing graph in Gn,m if it satisfies λ2 (G) ≥λ2 (G′ ) for all G′ ∈ Gn,m .
Definition 2 The set of all simple undirected graphs obtained by rewiring one edge in G ∈ Gn,m is called the neighborhood of G in Gn,m and denoted by Nn,m (G).
Definition 3 A graph G ∈ Gn,m is said to be an algebraic
connectivity locally maximizing graph in Gn,m if it satisfies
λ2 (G) ≥ λ2 (G′ ) for all G′ ∈ Nn,m (G).
The problem we tackle in this paper is to find algebraic
connectivity maximizing graphs and algebraic connectivity
locally maximizing graphs for the given number of nodes
and edges.

i=1
i = 2, 3, . . . , n − 1
i=nBy (4) and Lemma 2, we get following theorem.
Theorem 1 ([5]) The star graph S n is a algebraic connectivity maximizing graph in Gn,n−1 .
This result is also confirmed from Figs. 1 (a) and 2 (a).
3.4. Case where m = n
We next consider graphs having n nodes and n edges.
An example is the graph with E = {{1, 2}, {2, 3}, . . . , {n −1, n}, {n, 1}} which is called the cycle graph and denoted by
Cn . Eigenvalues of the Laplacian of the cycle graph are
known as follows.
Lemma 3 ([4]) Eigenvalues of the Laplacian of the cycle
graph Cn are given by)(
2π(k − 1),
λk (Cn ) = 2 1 − cosn3.2. Graphs Composed of 5 or 6 Nodes
Let us first consider the case where n is either 5 or 6. In
this case, all algebraic connectivity maximizing graphs canbe found by a brute-force search. Results for n = 5 aresummarized in Fig. 1 where algebraic connectivity maximizing graphs for G5,4 , G5,5 , . . . , G5,10 and the values of the(4)

k = 1, 2, . . . , n .

By Lemmas 1 and 3, we get the following theorem.
Theorem 2 The cycle graph Cn is an algebraic connectivity maximizing graph in Gn,n when 3 ≤ n ≤ 6.

- 57 -

(a) m = 4(b) m = 5(c) m = 6(d) m = 7(e) m = 8(f) m = 9(g) m = 10

Figure 1: Algebraic connectivity maximizing graphs for n = 5. The values of algebraic connectivity are (a) 1, (b) 1.381,(c) 2, (d) 2, (e) 3, (f) 3 and (g) 5.

Proof: Let G be any graph in Gn,n . Then the average degreeof G is 2 and there are two possible cases: 1) all nodes
have degree 2 and 2) not all nodes have degree 2. In theformer case, G must be the cycle graph Cn . The algebraic
connectivity of Cn is given by Lemma 3 as()
2π
λ2 (Cn ) = 2 1 − cos(5)nwhich is greater than 1 when 3 ≤ n ≤ 6. On the other hand,in the latter case, since at least one node has degree 1, we
have from Lemma 1 that λ2 (G) ≤ δ(G) = 1. Therefore,
the cycle graph Cn is an algebraic connectivity maximizing
graph in Gn,n for 3 ≤ n ≤ 6.
Let G be any graph in Gn,m and G′ ∈ Gn,m+1 be any
graph obtained by adding one edge to G. The following
lemma shows the relationship among eigenvalues of the
Laplacians of G and G′ .
Lemma 4 ([5]) Let G′ ∈ Gn,m+1 be a graph obtained byadding an edge to G ∈ Gn,m . Then we havestar graph is an algebraic connectivity maximizing graph in
Gn,n .
The graph with E = {{1, 2}, {2, 3}, . . . , {n − 1, n}} is called
the path graph and denoted by Pn . Concerning eigenvaluesof the Laplacian of Pn , the following result is known.
Lemma 5 ([4]) Eigenvalues of the Laplacian of the pathgraph Pn are given by)(π(k − 1), k = 1, 2, . . . , n .
λk (Pn ) = 2 1 − cosnTheorem 4 The cycle graph is an algebraic connectivity
locally maximizing graph in Gn,n .
Proof: Any graph obtained by removing an edge from thecycle graph Cn is isomorphic to the path graph Pn . Let G be
any graph belonging to the neighborhood Nn,n (Cn ) of Cn in
Gn,n . Then G is isomorphic to a graph obtained by adding
an edge to the path graph Pn . By Lemma 4, we have

λ1 (G) ≤ λ1 (G′ ) ≤ λ2 (G) ≤ . . . λn (G) ≤ λn (G′ ) .

λ2 (Pn ) ≤ λ2 (G) ≤ λ3 (Pn ) .

By Lemmas 1, 2, 3 and 4, we have the following theorem.
Theorem 3 A graph obtained by adding an edge to the stargraph S n is an algebraic connectivity maximizing graph in
Gn,n when n ≥ 6.
Proof: By Lemmas 2 and 4, the algebraic connectivity of
any graph obtained by adding an edge to the star graph is
1. We show that λ2 (G) ≤ 1 for any G ∈ Gn,n (n ≥ 6) inthe following. Since the average degree of G is 2, there
are two possible cases: 1) all nodes have degree 2 and 2)
not all nodes have degree 2. In the former case, G must
be the cycle graph Cn . By this fact and Eq.(5), λ2 (G) is
not greater than 1 for all n ≥ 6. On the other hand, in thelatter case, δ(G) = 1 because at least one node have degree
1. By Lemma 1, we have λ2 (G) ≤ δ(G) = 1. Therefore,
when n ≥ 6, any graph obtained by adding an edge to theAlso, by Lemmas 3 and 5, we have()
2π
λ3 (Pn ) = 2 1 − cos= λ2 (Cn ) .
n

(6)

(7)

Therefore, we have from (6) and (7) that λ2 (G) ≤ λ2 (Cn ).
Since G is any graph in Nn,n (Cn ), we conclude that the cycle graph Cn is an algebraic connectivity locally maximizing graph in Gn,n .

3.5. Complete Bipartite Graphs
A bipartite graph is a graph whose vertices can be divided into two disjoint sets V1 and V2 such that every edge
has one end in V1 and the other end in V2 . A complete bipartite graph is a bipartite graph in which there is an edge
between any pair of nodes i1 ∈ V1 and i2 ∈ V2 . The complete bipartite graph with partitions of size |V1 | = a and|V2 | = n − a (a ≤ n − a) is denoted Ka,n−a .

- 58 -

(a) m = 5(b) m = 6(g) m = 11(c) m = 7(h) m = 12(d) m = 8(i) m = 13(e) m = 9(j) m = 14(f) m = 10(k) m = 15

Figure 2: Algebraic connectivity maximizing graphs for n = 6. The values of algebraic connectivity are (a) 1, (b) 1, (c)1.268, (d) 2, (e) 3, (f) 3, (g) 3, (h) 4, (i) 4, (j) 4 and (k) 6.

Lemma 6 ([4]) Eigenvalues of the Laplacian of the complete bipartite graph Ka,n−a are given by


0,
i=1





i = 2, 3, . . . , a − 1 a,λi (Ka,n−a ) = 


n
−
a,
i
= a, . . . , n − 1



 n,
i=n
By Lemmas 1 and 6, we have the following theorem.
Theorem 5 If a − 2a2 /n < 1, the complete bipartite graphKa,n−a is an algebraic connectivity maximizing graph in
Gn,a(n−a) .
Proof: Let G be any graph in Gn,a(n−a) . The average degreeof G is given by(
2m 2a(n − a)a)2a2=
= 2a 1 −
=a+a−
.
n
n
n
n
If a − 2a2 /n < 1, this quantity is less than a + 1 and hence
the minimum degree of G is at most a. By this fact andLemma 1, we have λ2 (G) ≤ δ(G) ≤ a. On the other hand,
we have from Lemma 6 that λ2 (Ka,n−a ) = a. Therefore, thecomplete bipartite graph Ka,n−a is an algebraic connectivity
maximizing graph in Gn,a(n−a) .


4. Conclusions
In this paper, we have considered the problem of finding undirected graphs maximizing the algebraic connectivity for the given number of nodes and edges. We first introduced notions of algebraic connectivity maximizing graphs
and algebraic connectivity locally maximizing graphs. We
then proved some fundamental results about these notions.
Acknowledgments
This work was supported by KAKENHI 21560068.
References[1] R. Olfati-Saber, J. A. Fax and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. IEEE, vol.95, no.1, pp.215–233, 2007.
[2] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networks of dynamic agents,” in Proc. 2003
American Control Conference, pp.951–956, 2003.
[3] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Math. J., vol.23, no.98, pp.298–305,
1973.

Theorem 6 The complete bipartite graph Ka,n−a is an algebraic connectivity locally maximizing graph in Gn,a(n−a) .

[4] W. N. Anderson, Jr. and T. D. Morley, “Eigenvaluesof the Laplacian of a graph,” Linear and Multilinear
Algebra, vol.18, pp.141–125, 1985.

Proof: Let G be any graph in Nn,a(n−a) (Ka,n−a ). It is easily
seen that G has at least one node whose degree is a. By
this fact and Lemma 1, we have λ2 (G) ≤ δ(G) ≤ a. On
the other hand, we have from Lemma 6 that λ2 (Ka,n−a ) = a.
Therefore, the complete bipartite graph Ka,n−a is an algebraic connectivity locally maximizing graph in Gn,a(n−a) . [5] B. Mohar, “The Laplacian spectrum of graphs”
in Graph Theory, Combinatorics and Applications, Y. Alavi, G. Chartrand, O. Ollermann and
A. Schwenk, Eds. Wiley, New York, pp.871–898,
1991.

- 59 -