Maximizing Algebraic Connectivity in the Space ofGraphs with Fixed Number of Vertices and Edges
Author(s): Kohnosuke Ogiwara, Tatsuya Fukami and Norikazu Takahashi
Journal: IEEE Transactions on Control of Network Systems
Volume: 4
Number: 2
Pages: 359–368
Month: June
Year: 2017
DOI: 10.1109/TCNS.2015.2503561
Published Version: http://ieeexplore.ieee.org/document/7336529/c⃝2017IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing thismaterial for advertising or promotional purposes, creating new collective works, for resale
orredistribution to servers or lists, or reuse of any copyrighted component of this work in otherworks.

1

Maximizing Algebraic Connectivity in the Space ofGraphs with Fixed Number of Vertices and Edges
Kohnosuke Ogiwara, Tatsuya Fukami and Norikazu Takahashi, Member, IEEE

Abstract—The second smallest eigenvalue of the Laplacianmatrix, also known as the algebraic connectivity, characterizes
the performance of some dynamic processes on networks, suchas consensus in multiagent networks, synchronization of coupledoscillators, random walks on graphs, and so on. In a multiagent
network, for example, the larger the algebraic connectivity of
the graph representing interactions between agents is, the fasterthe convergence speed of a representative consensus algorithm is.
This paper tackles the problem of finding graphs that maximize
or locally maximize the algebraic connectivity in the space ofgraphs with a fixed number of vertices and edges. It is shownthat some well-known classes of graphs such as star graphs,
cycle graphs, complete bipartite graphs and circulant graphs
are algebraic connectivity maximizers or local maximizers undercertain conditions.
Index Terms—multiagent network, consensus algorithm, convergence rate, Laplacian matrix, algebraic connectivity

I. I NTRODUCTION
OW to reach a consensus is a fundamental problem
in multiagent networks. Many applications in the realworld such as data fusion in sensor networks, flocking, formation flight in space, synchronization of coupled oscillators
are closely related to the consensus problem in multiagent
networks [2]–[10]. In recent years, various protocols forreaching a consensus have been proposed [2], [3], [11]–[18].
As a representative example, let us consider the consensus
protocol proposed by Olfati-Saber and Murray [2]. This protocol is described by a set of linear differential equations,and some fundamental results on the convergence property
are obtained [2], [3]. First, the state value of each agent
always converges to the average of the initial state valuesof all agents, if the network satisfies some mild conditions.
Second, the rate of convergence is determined by the second
smallest eigenvalue of the Laplacian matrix, also known as thealgebraic connectivity [19], [20], of the graph, representing theinteractions between agents. In general, the algebraic connectivity varies in a wide range depending on the structure of thegraph even though the number of vertices and edges is fixed

HPart of this work was published in a conference paper [1]. However,the present paper is not just an extended version of it because there aremany differences. For example, new theoretical results such as Theorem 4,
Theorem 7 and some lemmas needed to prove these theorems are given. Also,background and related works are explained in more detail.
This work was partially supported by JSPS KAKENHI Grant Numbers
24560076, 23310104 and 15K00035.
K. Ogiwara and T. Fukami were with the Graduate School of Information
Science and Electrical Engineering, Kyushu University, Fukuoka, 819-0395
Japan.
N. Takahashi is with the Graduate School of Natural Scienceand Technology, Okayama University, Okayama 700-8530 Japan (email:takahashi@cs.okayama-u.ac.jp).

(see, e.g., [3]). Therefore, finding graphs that maximize thealgebraic connectivity under some constraints on the numberof vertices, the number of edges, the degree distribution, andso on is a fundamental problem for consensus in multiagent
networks.
Kim and Mesbahi [21] considered the problem of maximizing the algebraic connectivity of graphs with weighted
edges. In their problem setting, each vertex corresponds toa point mass and the weight of each edge is determined bya function of the distance between two end vertices of theedge. Furthermore, the distance between any two vertices isassumed to be greater than or equal to a positive constant.
For this constrained optimization problem, they proposed an
iterative algorithm based on a semidefinite program solver, andshowed through extensive simulations that it often leads to an
optimal solution. Kim [22] considered the problem of finding
an edge to be added to a given graph such that the algebraic
connectivity of the resulting graph is maximized, and proposed
a computationally efficient algorithm for solving the problem.
Rafiee and Bayen [23] considered two types of problems
related to the optimal topology design for multiagent networks.
One is the problem of finding a graph with weighted edges
that maximizes the algebraic connectivity under the constraintthat the number of edges with nonzero weight is less thanor equal to a given positive integer. The other is the problemof finding a graph with weighted edges that minimizes thenumber of edges with nonzero weight under the constraint thatthe algebraic connectivity is greater than or equal to a given
positive number. They formulated these problems as mixedinteger semidefinite programs (MISDP) and showed that these
programs can be solved by using an SDP solver. Dai andMesbahi [24] considered the optimal topology design problem
for dynamic networks in three different scenarios: i) findinga graph with unweighted edges that maximizes the algebraic
connectivity under the constraint that the number of edges
is bounded from above, ii) finding a graph with weighted
edges that maximizes the algebraic connectivity under theassumption that the weight of each edge is determined by afunction of two parameters associated with two end vertices
and the parameters are bounded from above and below, iii)
minimizing the time period required for agents to move fromthe given initial state to the given final state while obeying
the consensus dynamics. All of these problems are formulated
as mathematical programming problems and can be solved byappropriate solvers.
The problem of finding optimal graphs has also been studied
for the discrete-time consensus protocol. Xiao and Boyd [12]considered the problem of optimizing the communication

2

weights in the distributed averaging protocol for the fastest
convergence, and showed that it can be cast as an SDP. They
also introduced an ℓ1 regularized variant of the problem, andshowed that the weights and the topology of communication
are optimized simultaneously by solving it. On the other hand,
Delvenne [17] et al. proved that the optimal topology ofcommunication under the constraint that the out-degree of any
vertex is upper bounded by a given positive integer ν is given
by a de Bruijin graph. However, this result holds true only forthe case where the number of vertices is a power of ν.
The importance of the algebraic connectivity is not restricted
to consensus in multiagent networks. The algebraic connectivity is, as its name suggests, a measure that represents how wellconnected the network is, and closely related to the traditionalvertex and edge connectivities [19], [25]. It is thus very usefulfor designing robust networks. In fact, the algebraic connectivity played an important role in the design of various networks
such as computer networks [26]–[29] and air transportation
networks [30], [31]. The algebraic connectivity is also related
to the performance of some dynamic processes other thanconsensus on networks [32]–[34]. For example, a networkof dynamical units has a more robust synchronized state if
the algebraic connectivity is large, and random walks moveand disseminate efficiently in networks with large algebraic
connectivity [33].
In this paper, we consider the problem of finding undirected
and unweighted graphs that maximize or locally maximize
the algebraic connectivity in the space of graphs with a fixed
number of vertices and edges. We say that a graph locally maximizes the algebraic connectivity if its algebraic connectivity is
not less than any graph obtained from it by rewiring only one
edge. From a viewpoint of multiagent networks, this can beviewed as the problem of finding topologies of communication
between agents with which the network reaches a consensus
in the shortest or nearly shortest time, under the constraintthat the total power of communication is fixed. This is very
similar to the first scenario of Dai and Mesbahi. However, we
do not take a mathematical programming approach, but study
this problem analytically. We first prove that some well-knownclasses of graphs such as star graphs, cycle graphs, complete
bipartite graphs maximize the algebraic connectivity undercertain conditions. We then prove that cycle graphs, complete
bipartite graphs, and circulant graphs locally maximize thealgebraic connectivity.
The analysis and design of the network topology based on
the algebraic connectivity have also been extensively studied inapplied mathematics [35]–[47]. We mention here some of theexisting results related to the subject of this paper. Fallat and
Kirkland [36] studied the algebraic connectivity of unicycle
graphs with a given girth, and proved that any graph obtainedby adding one edge to a star graph maximizes the algebraic
connectivity among all unicycle graphs with the same numberof vertices and girth 3. A generalized version of this result will
be given in Section III. Belhaiza et al. [37] provided someresults on graphs with the maximum algebraic connectivity
for a given number of vertices and edges. Their results arevalid for the case where the number of edges is sufficiently
large, while many of the results in the present paper apply tothe case where the number of edges is small in the sensethat it is proportional to the number of vertices. Wang etal. [43] proved that the maximum of the algebraic connectivity
among all graphs with a given number of vertices and a given
diameter is achieved by a chain of cliques. Bıyıkoğlu andLeydold [45] proved that if a graph has the minimum algebraic
connectivity among all connected graphs with a given numberof vertices and edges then it must consist of a chain ofcliques. Sydney et al. [46] recently proposed an iterative
method based on edge rewiring to obtain a graph having
high algebraic connectivity. In addition to these works, there
are a number of theoretical results concerning the algebraic
connectivity (see, e.g., [40] and [44]). The present paper not
only extends some known results on graphs with the maximum
algebraic connectivity to more general ones but also takes a
new direction by introducing the problem of finding graphsthat locally maximize the algebraic connectivity, which has
not been studied before.
The rest of this paper is organized as follows. In Section II,
we review the consensus protocol of Olfati-Saber and Murray [2] and its convergence properties. We also demonstratethat the algebraic connectivity of a graph with a fixed numberof vertices and edges varies greatly depending on its structure.
In Section III, the notion of algebraic connectivity maximizing
graph is first introduced, and then some classes of thesegraphs are presented. In Section IV, the notion of algebraic
connectivity locally maximizing graph is introduced first, andthen some theoretical results on these graphs are given. Finally,
we conclude the paper in Section V.
II. BACKGROUND AND M OTIVATION
We consider networks of n agents labeled from 1 to nthat can interact with each other. The set of agents withwhich agent i can directly interact is denoted by Ni ⊆{1, 2, . . . , n} \ {i}. Suppose that each agent i has its own statevalue xi (t) where t represents time, and increase or decrease
it continuously based on the state values of agents in Ni .
Throughout this paper, we assume that interactions between
agents are time-invariant (or static) and symmetric, that is,j ∈ Ni if and only if i ∈ Nj . Under this setting, Olfati-Saberand Murray [2] proposed the state update rule described by∑ẋi (t) =(xj (t) − xi (t)), i = 1, 2, . . . , n ,
(1)
j∈Ni

and showed that the network∑n reaches an average consensus,that is, limt→∞ xi (t) =j=1 xj (0)/n for i = 1, 2, . . . , n,
if it is connected. Here, a multiagent network is said to beconnected if for any two different agents i and j there is asequence of agents i1 (= i), i2 , . . . , il (= j) such that ik+1 ∈Nik for k = 1, 2, . . . , l − 1.
Interactions between agents can be represented by a simple
undirected graph G = (V, E) where V = {1, 2 . . . , n} is theset of vertices representing n agents, and E is the set of edges
representing interactions between agents. In this paper, eachedge is expressed by an unordered pair of two different vertices
like {i, j}. A pair {i, j} is a member of E if and only if
agents i and j can directly interact with each other, that is,

3

10
9
8
state value

7

(a)

6
5
4
3
2

(b)

1
0

5

10

Fig. 1. Two graphs consisting of 10 vertices and nine edges. (a) Star graph.
(b) Path graph.

15

20
time

25

30

35

40

20
time

25

30

35

40

(a)
10

j ∈ Ni or equivalently i ∈ Nj . The Laplacian matrix of agraph G = (V, E) is defined by(2)

where A = (aij ) ∈ {0, 1}
is the adjacency matrix and
D = diag(d1 , d2 , . . . , dn ) is the degree matrix of the graph G.
Note that∑the components of D are determined by those of A
as di = j̸=i aij for i = 1, 2, . . . , n. By using the Laplacianmatrix L, Eq.(1) can be rewritten asn×nẋ(t) = −Lx(t)87state value

L=D−A

9

6
5
4
3
2
1
0

(3)

where x(t) = (x1 (t), x2 (t), . . . , xn (t))T .
Let the eigenvalues of L be denoted by λ1 ≤ λ2 ≤ · · · ≤λn . It is well known that i) all eigenvalues of L are real andnonnegative, ii) λ1 is always zero, and iii) λ2 is nonzero if
and only if G is connected (see, e.g., [25]). Therefore, theconvergence rate of the consensus algorithm (1) is determinedby the second smallest eigenvalue of L, that is, the algebraic
connectivity, if the network is connected [3].
The algebraic connectivity of a graph varies greatly depending on its structure, even though the number of vertices
and edges is fixed. It is illustrated in [3] that a small-world
network with 100 nodes and 300 links reaches an averageconsensus about 22 times faster than a regular lattice withthe same number of nodes and links. Here, we consider amuch simpler case where a star graph composed of 10 vertices
and a path graph composed of the same number of vertices
are compared (see Fig. 1). Note that both graphs have nineedges. The algebraic connectivity of the star graph is 1 andthat of the path graph is about 0.0978. This indicates that theformer reaches an average consensus about 10 times fasterthan the latter. In fact, this estimation is confirmed by Fig.2
which illustrates trajectories of state values when xi (0) = i
for i = 1, 2, . . . , 10.
In the following sections, by a graph, we mean a simple
undirected graph. The set of all graphs composed of nvertices and m edges is denoted by Gn,m . For each graphG ∈ Gn,m , the eigenvalues of its Laplacian matrix are denotedby λ1 (G), λ2 (G), . . . , λn (G), instead of λ1 , λ2 , . . . , λn , inorder to indicate explicitly the graph under consideration. As
mentioned above, we assume without loss of generality thateigenvalues are sorted in ascending order as 0 = λ1 (G) ≤

5

10

15

(b)
Fig. 2. Trajectories of the state values of 10 agents generated by the consensus
algorithm (1) for (a) the star graph and (b) the path graph. Because thealgebraic connectivity of the star graph is about 10 times that of the pathgraph, the convergence rate of the consensus algorithm for the star graph isabout 10 times faster than that for the path graph, though both graphs havethe same number of vertices and edges.

λ2 (G) ≤ . . . ≤ λn (G). Then the algebraic connectivity of agraph G is denoted by λ2 (G).
III. A LGEBRAIC C ONNECTIVITY M AXIMIZING G RAPHS
A. Problem Setting and Brute-Force Search
In this section, we consider the problem of finding a graphG ∈ Gn,m for each pair (n, m), such that λ2 (G) is not lessthan any other graphs in Gn,m . We call such a graph an
Algebraic Connectivity Maximizing (ACM) graph in Gn,m .
Because the convergence rate of the consensus algorithm(1) is determined by the algebraic connectivity of the graphrepresenting interactions between agents, each ACM graphshows how interactions should be performed by agents forthe fastest consensus.
We first identify all ACM graphs in Gn,m for small n by abrute-force search. To be more specific, for each pair (n, m)such that 5 ≤ n ≤ 7 and n − 1 ≤ m ≤ n(n − 1)/2,
we enumerate all graphs in Gn,m , calculate their algebraic
connectivity, and determine the graphs that have the highest
algebraic connectivity. Results for n = 5, 6 and 7 aresummarized in Figs. 3, 4 and 5, respectively. From theseresults, some important facts are observed: i) Gn,m can have4

more than one ACM graph, ii) the star graph Sn is the unique
ACM graph in Gn,n−1 for n = 5, 6 and 7, iii) the cycle graph
Cn is an ACM graph in Gn,n for n = 5 and 6, but not forn = 7, iv) for (n, m) = (5, 4), (5, 6), (6, 5), (6, 8), (7, 6)(7, 10) and (7, 12), Gn,m has the unique ACM graph which
is a complete bipartite graph, v) for (n, m) = (5, 5), (6, 6),(6, 9), (6, 12) and (7, 14), a circulant graph is contained in theset of ACM graphs in Gn,m .
The MISDP method [24] can also be used to find an ACM
graph in Gn,m for each pair of n and m. However, we shouldnote that it cannot be directly applied to the problem of finding
all ACM graphs in Gn,m . In fact, the MISDP method generates
only one graph, which is isomorphic to the right one shownin Fig. 5(k), when it is applied to the case where (n, m) =(7, 16) [24].
B. Theoretical Analysis
Before proceeding to the main results of this section, we
introduce some known results [19], [20], [48] about eigenvalues of the Laplacian matrix. Proofs of Lemmas 1, 2, 3 and 4
can be found in [20]. Proofs of Lemmas 5 and 6 can be foundin [19] and [48], respectively.
Lemma 1: Eigenvalues of the Laplacian matrix of the stargraph Sn with n ≥ 3 are given by 0, i = 1 ,1, i = 2, 3, . . . , n − 1 ,λi (Sn ) =
n, i = n .
Lemma 2: Eigenvalues of the Laplacian matrix of the pathgraph Pn are given by()π(i − 1)λi (Pn ) = 2 1 − cos, i = 1, 2, . . . , n .
nLemma 3: Eigenvalues of the Laplacian matrix of the cycle
graph Cn are given by)(2π(⌈(i − 1)/2⌉), i = 1, 2, . . . , nλi (Cn ) = 2 1 − cosnTheorem 1: For n = 3, 4, 5 and 6, the cycle graph Cn is an
ACM graph in Gn,n .
Proof: Let G be any graph in Gn,n with n ≥ 3. Then,
depending on the degree distribution, there are two possible
cases: one is that all vertices have degree 2 and the second isthat at least one vertex has degree less than 2. In the former
case, G must be the cycle graph Cn . The algebraic connectivityof Cn is given by Lemma 3 as)(
2π
λ2 (Cn ) = 2 1 − cos(4)nwhich is greater than 1 if 3 ≤ n ≤ 6. In the latter case, wehave from Lemma 5 that λ2 (G) ≤ δ(G) ≤ 1. Therefore, thecycle graph Cn is an ACM graph in Gn,n if 3 ≤ n ≤ 6.
Theorem 2: For any n ≥ 6, any graph obtained by adding
an edge to the star graph Sn is an ACM graph in Gn,n .
Proof: By Lemmas 1 and 6, the algebraic connectivity of
any graph obtained by adding an edge to the star graph Snwith n ≥ 6 is 1. So it suffices for us to show that λ2 (G) ≤ 1
for any G ∈ Gn,n with n ≥ 6. Since the average degree of G
is 2, there are two possible cases: one is that all vertices havedegree 2 and the other is that at least one vertex has degree lessthan 2. In the former case, G must be the cycle graph Cn . By
this fact and Eq.(4), λ2 (G) is not greater than 1 for all n ≥ 6.
In the latter case, by Lemma 5, we have λ2 (G) ≤ δ(G) ≤ 1.
Therefore, any graph obtained by adding an edge to the stargraph Sn is an ACM graph in Gn,n if n ≥ 6.
Graphs covered by Theorems 1 and 2 are shown in
Figs. 3(b), 4(b) and 5(b).
As far as the case where n ≥ 6 is considered, Theorem 2
is a generalization of a theorem proved by Fallat and Kirkland [36, Theorem 4.14] which says that any graph obtained byadding an edge to the star graph Sn maximizes the algebraic
connectivity among all unicycle graphs with n vertices andgirth 3.
We next consider complete bipartite graphs.
Theorem 3: For any n ≥ 3 and any integer k satisfying
1 ≤ k ≤ ⌊n/2⌋ andwhere ⌈r⌉ represents the smallest integer not less than r.
Lemma 4: Eigenvalues of the Laplacian matrix of thecomplete bipartite graph Kk,n−k with 1 ≤ k ≤ ⌊n/2⌋ aregiven by0,i = 1,
k,i = 2, 3, . . . , n − k ,λi (Kk,n−k ) =n − k, i = n − k + 1, . . . , n − 1 ,n,
i = n,

2k 2
< 1,
(5)
n
the complete bipartite graph Kk,n−k is an ACM graph in
Gn,k(n−k) .
Proof: Let G be any graph in Gn,k(n−k) . The average
degree of G is given by()
2m
2k(n − k)k
2k 2== 2k 1 −
=k+k−
.
n
n
n
n

where ⌊r⌋ represents the largest integer not greater than r.
Lemma 5: If G is not a complete graph then λ2 (G) ≤ δ(G)where δ(G) is the minimum degree of G.
Lemma 6: Let G′ ∈ Gn,m+1 be a graph obtained by adding
an edge to G ∈ Gn,m . Then we haveIf (5) is satisfied, this quantity is less than k + 1 and hence theminimum degree of G is at most k. By this fact and Lemma 5,
we have λ2 (G) ≤ δ(G) ≤ k. On the other hand, we havefrom Lemma 4 that λ2 (Kk,n−k ) = k. Therefore, the complete
bipartite graph Kk,n−k is an ACM graph in Gn,k(n−k) .
Solving the inequality (5) for k under the assumptions thatn ≥ 3 and 1 ≤ k ≤ ⌊n/2⌋, we obtain the following result.
Corollary 1: If two integers n and k satisfy one of thefollowing three conditions then the complete bipartite graph
Kk,n−k is an ACM graph in Gn,k(n−k) .

λ1 (G) ≤ λ1 (G′ ) ≤ λ2 (G) ≤ λ2 (G′ ) · · · ≤ λn (G) ≤ λn (G′ ) .
Let us first consider the case where m = n. In this case,
we obtain the following two results.

k−5Fig. 3. Algebraic connectivity maximizing graphs in G5,m (m = 4, 5, . . . , 9). The values of algebraic connectivity are (a) 1, (b) 1.382, (c) 2, (d) 2, (e) 3and (f) 3.

Fig. 4. Algebraic connectivity maximizing graphs in G6,m (m = 5, 6, . . . , 14). 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.

Fig. 5. Algebraic connectivity maximizing graphs in G7,m (m = 6, 7, . . . , 20). The values of algebraic connectivity are (a) 1, (b) 1, (c) 1, (d) 1.586, (e) 2,(f) 2.139, (g) 3, (h) 3, (i) 3.198, (j) 4, (k) 4, (l) 4, (m) 5, (n) 5, (o) 5.

1) 3 ≤ n ≤ 7 and 1 ≤ k ≤ ⌊n/2⌋
2) n ≥ 8 and k = 1√
3) n ≥ 8 and (n + n2 − 8n)/4 < k ≤ ⌊n/2⌋
Because the inequality (5) is satisfied with k = 1 for any
n ≥ 3, we have the following result as a special case of
Theorem 3.
Corollary 2 (Mohar [48]): For any n ≥ 3, the star graph
Sn is an ACM graph in Gn,n−1 .
Graphs covered by Theorem 3 are shown in Figs. 3(a), 3(c),4(a), 4(d), 4(e), 5(a), 5(e), and 5(g). These graphs correspondto the cases where (n, k) = (5, 1), (5, 2), (6, 1), (6, 2), (6, 3),(7, 1), (7, 2) and (7, 3). The inequality (5) is also satisfied
with (n, k) = (8, 3), (8, 4), (9, 4), (10, 4), (10, 5), and so on.
Looking at these pairs, we expect that the complete bipartite
graph Kk,n−k is an ACM graph in Gn,k(n−k) if k is close ton/2. In fact, we obtain the following result as a special caseof Theorem 3.
Corollary 3: For any n ≥ 3 and any integer k satisfying
⌊
⌋
⌊n⌋
n−1
,
(6)
≤k≤
2
2
the complete bipartite graph Kk,n−k is an ACM graph in
Gn,k(n−k) .

Proof: Suppose first that n is an even number. Then n canbe expressed as n = 2l where l is an integer not less than 2.
Furthermore, the condition (6) is equivalent to l − 1 ≤ k ≤ l.
If n = 2l and k = l − 1, we have
2k 22(l − 1)2k−
= l−1−n2ll−1={l − (l − 1)}
l
l−1
=
< 1.
l
If n = 2l and k = l, we have
2k 2
2l2
k−
=l−
= l − l = 0 < 1.
n2lNamely, if n is an even number and k is either n/2 − 1 orn/2, the inequality (5) is satisfied. Suppose next that n is an
odd number. Then n can be expressed as n = 2l − 1 where lis any integer not less than 2. Furthermore, the condition (6)is equivalent to k = l − 1. If n = 2l − 1 and k = l − 1, theinequality (5) is satisfied because
k−

2k 2
n

= l−1−=

2(l − 1)2
2l − 1l−1{(2l − 1) − 2(l − 1)}2l − 1

6

Fig. 7. Relationship between G and G′′ . (a) G has a cycle containing avertex with degree greater than two. (b) G′′ has two connected components′′
G′′
1 and G2 .

Fig. 6. Three possible topologies of a connected graph G ∈ Gn,n+1 with
δ(G) ≥ 2.

l−1< 1.
2l − 1
Therefore, by Theorem 3, any complete bipartite graph
Kk,n−k satisfying (6) is an ACM graph in Gn,k(n−k) .
We next consider graphs obtained by adding a small numberof edges to a star graph. The following two lemmas are needed
in later discussion.
Lemma 7: Let n and k be positive integers such that n ≥ 4
and 1 ≤ k ≤ n. If G ∈ Gn,n+k is connected and δ(G) ≥ 2
then there are 2k edges in G such that the removal of theseedges results in a linear forest with k components, where alinear forest is a graph in which each component is a path.
Proof: We prove Lemma 7 by mathematical induction. As
the initial step, we will prove the following two statements:i) if G ∈ G4,4+k and k ∈ {1, 2} then there are 2k edges
in G such that the removal of these edges results in a linear
forest with k components, ii) for any n ≥ 5, if G ∈ Gn,n+1 isconnected and δ(G) ≥ 2 then there exist two edges in G suchthat the removal of these edges results in a path graph. For
the first statement, by considering any graph in G4,5 and theunique graph in G4,6 , one can immediately see that it is true.
So we consider only the second one. Because G has n + 1
edges and δ(G) ≥ 2, the distribution of degrees is restricted totwo cases. The first case is that one vertex has degree four andother n − 1 vertices have degree two. In this case, G always
has the topology shown in Fig. 6 (a). It is easily seen from thefigure that we can obtain a path graph by removing two edges,
say, {i1 , i2 } and {i1 , i4 }. The second case is that two vertices
have degree three and other n − 2 vertices have degree two. In
this case, G always has one of two possible topologies shownin Fig. 6 (b) and (c). In either type of graph, we can obtain apath graph by removing two edges, say, {i1 , i3 } and {i2 , i6 }.
As the inductive step, we will prove that the statement ofLemma 7 holds true for n = n∗ and k = k ∗ under theassumption that it holds true for n = 4, 5, . . . , n∗ − 1 and=for n = n∗ and k = 1, 2, . . . , k ∗ − 1, where n∗ is any integer
greater than four and k ∗ is any integer such that 2 ≤ k ∗ ≤ n∗ .
Because G is not a tree, it has at least one cycle. Moreover,because G itself is not a cycle graph, any cycle in G contains
at least one vertex with degree greater than two. Hence G has
an edge {i1 , i2 } such that it is in a cycle and the vertex i1 hasdegree greater than two, as shown in Fig. 7 (a). Let G′ be thegraph obtained from G by removing the edge {i1 , i2 }. Then,
G′ belongs to Gn∗ ,n∗ +k∗ −1 , G′ is connected, and all vertices
except i2 have degree greater than one in G′ . In the remainderof the proof, we shall consider two possible cases dependingon the degree of the vertex i2 .
First, let us consider the case where i2 has degree greaterthan one in G′ . By the assumption, there are 2(k ∗ −1) edges in
G′ such that a linear forest with k ∗ −1 components is obtained
from G′ by removing those edges. Note here that at least one
component has more than one vertex. This is because k ∗ −1 isless than n∗ . So, by removing an edge in such a component, we
can finally obtain a linear forest with k ∗ components. The total
number of edges removed from G is 1 + 2(k ∗ − 1) + 1 = 2k ∗ .
Next, let us consider the case where i2 has degree one in
G′ . In this case, there exists a path in G′ starting at i2 , visitingsome vertices with degree two, and ends at a vertex i3 with
degree greater than two. Let n1 be the length of the path. Then
we have 1 ≤ n1 ≤ n∗ − 1. Let G′′ be the graph obtained
from G′ by removing the last edge of the path, that is, theedge having i3 as one of its endpoints. Then G′′ has twocomponents; one, denoted by G′′1 , is a path having n1 vertices
and the other, denoted by G′′2 , is a connected graph havingn∗ − n1 vertices and n∗ − n1 + k ∗ − 1 edges, as shown in
Fig. 7 (b). If k ∗ − 1 ≤ n∗ − n1 then, by the assumption,
there are 2(k ∗ − 1) edges in G′′2 such that the removal ofthese edges from G′′2 results in a linear forest with k ∗ − 1components. This implies that we can obtain a linear forest
with k ∗ components from G by removing 2+2(k ∗ −1) = 2k ∗edges. If k ∗ − 1 > n∗ − n1 then we obtain a linear forest withn∗ − n1 components from G′′2 by removing all edges. Also,
we obtain a linear forest with k ∗ − n∗ + n1 components from
G′′1 by removing k ∗ − n∗ + n1 − 1 edges. Here, we shouldnote that k ∗ − n∗ + n1 − 1 is positive due to the assumptionthat k ∗ − 1 > n∗ − n1 and less than n1 due to the assumptionthat k ∗ ≤ n∗ . In summary, we can obtain a linear forest with(n∗ − n1 ) + (k ∗ − n∗ + n1 ) = k ∗ components from G by

7removing 2 + (n∗ − n1 + k ∗ − 1) + (k ∗ − n∗ + n1 − 1) = 2k ∗edges.
Lemma 8: Let n and k be positive integers such that n ≥5k + 4. If G ∈ Gn,n−k is a linear forest with k components
then λ2k+2 (G) ≤ 1.
Proof: Let Gj be the j-th component of G and let
λj1 (Gj ) ≤ λj2 (Gj ) ≤ · · · ≤ λjnj (Gj ) be eigenvalues of
the Laplacian matrix of Gj , where nj = |V (Gj )|. Then,{λi (G) | i = 1, 2, . . . , n} = {λji (Gj ) | j = 1, 2, . . . , k; i =1, 2, . . . , nj }. It follows from Lemma 2 that()π(i − 1)λji (Gj ) = 2 1 − cos, i = 1, 2, . . . , nj .
njnBecause λji (Gj ) ≤ 1 if and only if i ≤ ⌊ 3j ⌋ + 1, the numberof i ∈ {1, 2, . . . , n} such that λi (G) ≤ 1 is given by
k (⌊
∑
nj ⌋

3

j=1

k ⌊
) ∑
nj ⌋
+1 =
+k.
3
j=1

∑k
∑k
n
Here, because n = j=1 nj = j=1 (3⌊ 3j ⌋+(nj mod 3)) ≥5k + 4 and nj mod 3 ≤ 2, we have
k ⌊
∑
nj ⌋
j=1

3

+ k ≥ 2k + 2 .

Therefore, we conclude that λ2k+2 (G) ≤ 1.
We are now ready to present one of the main results of thissection.
Theorem 4: Let n and k be any positive integers such thatn ≥ 5k + 4. The graph obtained by adding k + 1 edges to thestar graph Sn is an ACM graph in Gn,n+k .
Proof: We first note that n is necessarily greater than orequal to 9. Let G∗ be any graph obtained from the star graph
Sn by adding k + 1 edges. Here, we see that k + 1 < n − 3
because the inequalities k + 1 ≤ (n − 4)/5 + 1 = (n + 1)/5 <n − 3 follows from n ≥ 5k + 4 and n ≥ 9. From this fact
together with Lemmas 1 and 6, we have λ2 (G∗ ) = 1. Hence,
it suffices for us to show that λ2 (G) ≤ 1 for any G ∈ Gn,n+k .
Suppose first that δ(G) = 1. Then, by Lemma 5, we have
λ2 (G) ≤ δ(G) = 1. Suppose next that δ(G) ≥ 2. Then, by
Lemma 7, we can choose 2k edges from E(G) such that a
linear forest G′ composed of k components is obtained fromG by removing the 2k edges. Furthermore, by Lemmas 6 and8, we have λ2 (G) ≤ λ2k+2 (G′ ) ≤ 1.
Theorem 4 can be rewritten in terms of the number ofvertices and edges as follows.
Corollary 4: Let n and m be any positive integers such thatn ≥ 9 and n + 1 ≤ m ≤ (6n − 4)/5. The graph obtained byadding m − (n − 1) edges to the star graph Sn is an ACM
graph in Gn,m .
IV. A LGEBRAIC C ONNECTIVITY L OCALLY M AXIMIZINGG RAPHSA. Problem Setting
In the previous section, we have given some classes of ACM
graphs. However, Figs. 3–5 contain many graphs that are notincluded in any of these classes. In this sense, the results inthe previous section are not sufficient to characterize all ACM
graphs.
In this section, we consider the problem of finding graphs
G ∈ Gn,m such that the algebraic connectivity of G is notless than that of any graph obtained from G by rewiring anedge, that is, removing an edge from and adding a new edge to
G. In the remainder of this section, such a graph is called an
Algebraic Connectivity Locally Maximizing (ACLM) graph in
Gn,m . Also, the set of all graphs obtained from G ∈ Gn,m byrewiring an edge is called the neighborhood of G in Gn,m , anddenoted by Nn,m (G). Then a graph G ∈ Gn,m is an ACLM
graph if and only if λ2 (G) ≥ λ2 (G′ ) for all G′ ∈ Nn,m (G).
Hence, in order to prove that G is an ACLM graph in Gn,m ,we do not have to consider all graphs in Gn,m but just in
Nn,m (G) which is much smaller than Gn,m .
It is apparent from the definitions of ACM and ACLM
graphs that if G is an ACM graph in Gn,m then it is necessarily
an ACLM graph in Gn,m . In other words, the set of all ACM
graphs in Gn,m is contained in the set of all ACLM graphs
in Gn,m . Although we do not directly consider ACM graphs
in this section, we may obtain new insight into ACM graphs
through the analysis of ACLM graphs. In particular, for somegraphs in Figs. 3–5 that the results in the previous section
cannot be applied to, we may be able to prove that they are
ACLM graphs.
Another important aspect of ACLM graphs is that each ofthem has a locally optimal topology in the sense that thealgebraic connectivity cannot be increased no matter whichedge is rewired. This means that any local search algorithm
based on edge rewiring (see, e.g., [46]) stops at an ACLM
graph. Each ACLM graph is thus expected to have a relatively
high algebraic connectivity. Therefore, the analysis of ACLM
graphs is important not only for understanding ACM graphs
but also for identifying suboptimal topologies.
B. Theoretical Analysis
We first consider cycle graphs.
Theorem 5: The cycle graph Cn is an ACLM graph in Gn,n .
Proof: Any graph obtained from Cn by removing an edge
is isomorphic to the path graph Pn . Let G be any graphbelonging to Nn,n (Cn ). Then G is isomorphic to a graphobtained from Pn by adding an edge. By Lemma 6, we have
λ2 (Pn ) ≤ λ2 (G) ≤ λ3 (Pn ) .
Also, by Lemmas 2 and 3, we have()
2π
λ3 (Pn ) = 2 1 − cos= λ2 (Cn ) .
n

(7)

(8)

Therefore, we have from (7) and (8) that λ2 (G) ≤ λ2 (Cn ).
Since G is any graph in Nn,n (Cn ), we conclude that the cycle
graph Cn is an ACLM graph in Gn,n .
Because the cycle graph Cn is not an ACM graph for n ≥ 7,
this result implies that not all ACLM graphs are ACM graphs.
We next consider complete bipartite graphs.
Theorem 6: For any positive integers n and k satisfying
2 ≤ k ≤ ⌊n/2⌋, the complete bipartite graph Kk,n−k is an
ACLM graph in Gn,k(n−k) .

8Proof: Let G be any graph in Nn,k(n−k) (Kk,n−k ) with2 ≤ k ≤ ⌊n/2⌋. It is easily seen that G has at least one
vertex of which degree is k. By this fact and Lemma 5,
we have λ2 (G) ≤ δ(G) ≤ k. On the other hand, we havefrom Lemma 4 that λ2 (Kk,n−k ) = k. Therefore, the complete
bipartite graph Kk,n−k is an ACLM graph in Gn,k(n−k) .
Theorems 3 and 6 are closely related to a conjecture madeby Kolokolnikov [47, Conjecture 1.5] which asserts that thecomplete bipartite graph K2,n−2 is an ACM graph. In fact,
Theorem 3 proves that it holds true for n ≤ 7 and Theorem 6
indicates that it may also be true for n ≥ 8. However, theconjecture still remains an open problem.
We finally consider circulant graphs. A circulant graph is agraph such that its adjacency matrix is a circulant matrix.
Theorem 7: If G ∈ Gn,m is a circulant graph with n being
odd then G is an ACLM graph in Gn,m . If G ∈ Gn,m is acirculant graph with n being even and if the adjacency matrix
A = (aij ) of G satisfies
n

2

2
∑

n

a1j (−1)j + a1, n2 +1 (−1) 2 > 0

(9)

j=2

then G is an ACLM graph in Gn,m .
Proof: If the Laplacian matrix of G is a circulant matrix,
its eigenvalues can be expressed in an explicit form as()
n∑2πi(j − 1)
ψi = d1 −a1j cos, i = 0, 1, . . . , n − 1nj=2∑nwhere d1 =j=2 a1j . Here, we should note that ψ0 = 0
and ψi = ψn−i for i = 1, 2, . . . , n − 1. We should also
note that a1j = a1,n+2−j for j = 2, 3, . . . , ⌊ n+1
2 ⌋ because
A is not only circulant but also symmetric. Let us firstconsider the case where n is odd. In this case, we have
λ2 (G) = λ3 (G), λ4 (G) = λ5 (G), . . . , λn−1 (G) = λn (G).
Let G′ ∈ Gn,m+1 be any graph obtained from G by adding
an edge, and G′′ ∈ Gn,m be any graph obtained from G′
by removing an edge. Then we have from Lemma 6 thatλ2 (G) ≤ λ2 (G′ ) ≤ λ3 (G) and λ1 (G′ ) ≤ λ2 (G′′ ) ≤ λ2 (G′ ).
These inequalities and the fact that λ2 (G) = λ3 (G) leads to
λ2 (G′′ ) ≤ λ2 (G), which means that G is an ACLM graph in
Gn,m . Let us next consider the case where n is even. In thiscase, we have ψi = ψn−i for i = 1, 2, . . . , n2 − 1 andψ n2= d1 −n∑

a1j cos π(j − 1)j=2n

= d1 + 22∑na1j (−1)j + a1, n2 +1 (−1) 2 .

j=2

If G satisfies (9) then we have from Lemma 5 that λ2 (G) ≤δ(G) = d1 < ψ n2 . Hence there exists an i ∈ {1, 2, . . . , n2 − 1}such that ψi = ψn−i = min1≤j≤n−1 {ψj }, which implies thatλ2 (G) = λ3 (G). Then, by using the same argument as above,
we can conclude that G is an ACLM graph in Gn,m .
As a special case of Theorem 7, we have the following
lemma.

Fig. 8. A graph G ∈ G10,30 that is a circulant graph but not an ACLM
graph.

Corollary 5: If G ∈ Gn,m is a circulant graph with n being
even and the adjacency matrix A = (aij ) of G satisfies{
1, j = 2, n2 + 1, n ,a1j =0, otherwise ,then G is an ACLM graph in Gn,m .
Proof: If G satisfies the conditions then the left-hand sidenof (9) becomes 2 + (−1) 2 , which is always positive.
Note that not all circulant graphs are ACLM graphs. As asimple example, let us consider the circulant graph G ∈ G10,30
shown in Fig. 8. Substituting a12 = a13 = a15 = 1 anda14 = a16 = 0 into the left-hand side of (9), we have
n

2

2
∑

n

a1j (−1)j + a1, n2 +1 (−1) 2 = −2 < 0 ,j=2

which suggests the possibility that G is not an ACLM graph.
In fact, we have λ2 (G)(= 4) < λ2 (G′ )(= 4.1391421 · · · ),where G′ is the graph obtained from G by removing the edge
{1, 3} and adding the edge {1, 6}.
C. How Close are ACLM graphs to ACM graphs?
For each of the ACLM graphs presented in this section, we
see how close its algebraic connectivity is to that of ACM
graphs with the same number of vertices and edges.
We first consider the cycle graph Cn . As shown in Figs. 3
and 4, Cn is an ACM graph in Gn,n for n = 5 and 6. However,its algebraic connectivity λ2 (Cn ) = 2(1−cos 2π/n) converges
to 0 as n goes to infinity. On the other hand, the algebraic
connectivity of any ACM graph in Gn,n is 1, as shown in the
proof of Theorem 2. Therefore, we can conclude that the cycle
graph Cn is far from the ACM graph for large n.
We next consider the complete bipartite graph Kk,n−k with2 ≤ k ≤ ⌊n/2⌋. As mentioned in Section III, Kk,n−k is an
ACM graph in Gn,k(n−k) for (n, k) = (5, 2), (6, 2), (6, 3),(7, 2), (7, 3), (8, 3), (8, 4), (9, 4), (10, 4) and (10, 5). The
algebraic connectivity of Kk,n−k is k (see Lemma 4). On theother hand, the algebraic connectivity of any G ∈ Gn,k(n−k)
is less than 2k because the minimum degree of G is less thanor equal to 2k(n − k)/n = 2k − 2k 2 /n < 2k. This means thatthe algebraic connectivity of Kk,n−k with 2 ≤ k ≤ ⌊n/2⌋ isgreater than the half of that of ACM graphs in Gn,k(n−k) .
We finally consider circulant graphs. As shown in Figs. 3,
4 and 5, all circulant graphs in Gn,m with 5 ≤ n ≤ 7 except
C7 are ACM graphs in Gn,m . However, it is difficult to draw
a general conclusion about circulant graphs because a variety

9of graphs are contained. So we focus our attention on two
extreme cases. One is the case where a12 = a1n = 1 anda1j = 0 for j = 3, 4, . . . , n − 1. The other is the case where
n is even, a1j = 1 if j is even, and a1j = 0 otherwise. The
former corresponds to the cycle graph Cn which is far from the
ACM graph for large n. The latter corresponds to the complete
bipartite graph Kn/2,n/2 which is an ACM graph in Gn,n2 /4(see Corollary 3).
V. C ONCLUDING R EMARKS
We have studied the problem of finding undirected andunweighted graphs that maximize the algebraic connectivity inthe space of such graphs with a fixed number of vertices andedges. This problem is closely related to consensus and otherdynamic processes in networked systems. We have introduced
notions of ACM and ACLM graphs, and presented several
theoretical results on these graphs. The results are summarizedin Tables I and II where some classes of ACM and ACLM
graphs are presented. Tables I and II also show the average
degree and its minimum and maximum values for each classof graphs. The authors believe that these results provide useful
information for those who want to design some network so thatit has the highest or a relatively high algebraic connectivity.
However, because Tables I and II cover only a small part of thecollection of ACM graphs obtained by a brute-force search,
it is still needed to identify other classes of ACM or ACLM
graphs as many as possible. Also, in view of the application
to networks of agents, it is important to consider the problemof maximizing algebraic connectivity under some constraint
on the degree of each vertex. For example, it is interesting tofocus our attention on regular graphs.
ACKNOWLEDGMENT
The authors would like to thank anonymous reviewers
for their valuable comments and suggestions to improve thequality of the paper.
R EFERENCES[1] K. Ogiwara and N. Takahashi, “On topology of networked multiagent systems for fast consensus,” in Proceedings of 2011 International
Symposium on Nonlinear Theory and its Applications, September 2011,
pp. 56–59.
[2] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networksof dynamic agents,” in Proceedings of the 2003 American Control
Conference, June 2003, pp. 951–956.
[3] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE,
vol. 95, no. 1, pp. 215–233, January 2007.
[4] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobileautonomous agents using nearest neighbor rules,” IEEE Transactions on
Automatic Control, vol. 48, no. 6, pp. 988–1001, June 2003.
[5] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor
fusion based on average consensus,” in Proceedings of the FourthInternational Symposium on Information Processing in Sensor Networks,
April 2005, pp. 63–70.
[6] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms
and theory,” Automatic Control, IEEE Transactions on, vol. 51, no. 3,
pp. 401–420, March 2006.
[7] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip
algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6,
pp. 2508–2530, June 2006.

[8] G. Chen and Z. Duan, “Network synchronizability analysis: A graphtheoretic approach,” Chaos: An Interdisciplinary Journal of Nonlinear
Science, vol. 18, no. 3, pp. 037 102–037 102, 2008.
[9] M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent
Networks. Princeton: Princeton University Press, 2010.
[10] Z. Li, Z. Duan, G. Chen, and L. Huang, “Consensus of multiagent
systems and synchronization of complex networks: A unified viewpoint,”
IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57,
no. 1, pp. 213–224, January 2010.
[11] R. Olfati-Saber and R. M. Murray, “Consensus problems in networksof agents with switching topology and time-delays,” IEEE Transactions
on Automatic Control, vol. 49, no. 9, pp. 1520–1533, September 2004.
[12] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,”
Systems & Control Letters, vol. 53, pp. 65–78, September 2004.
[13] W. Ren and R. W. Beard, “Consensus seeking in multiagent systems
under dynamically changing interaction topologies,” IEEE Transactions
on Automatic Control, vol. 50, no. 5, pp. 655–661, May 2005.
[14] Y. Hatano and M. Mesbahi, “Agreement over random networks,” IEEE
Transactions on Automatic Control, vol. 50, no. 11, pp. 1867–1872,
November 2005.
[15] F. Fagnani and S. Zampieri, “Average consensus with packet dropcommunication,” SIAM Journal on Control and Optimization, vol. 48,
no. 1, pp. 102–133, 2009.
[16] M. Huang and J. H. Manton, “Coordination and consensus of networked
agents with noisy measurements: stochastic algorithms and asymptotic
behavior,” SIAM Journal on Control and Optimization, vol. 48, no. 1,
pp. 134–161, 2009.
[17] J.-C. Delvenne, R. Carli, and S. Zampieri, “Optimal strategies in the
average consensus problem,” Systems & Control Letters, vol. 58, pp.
759–765, 2009.
[18] W. Ni and D. Cheng, “Leader-following consensus of multi-agent
systems under fixed and switching topologies,” Systems & Control
Letters, vol. 59, no. 3, pp. 209–217, March–April 2010.
[19] M. Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematical Journal, vol. 23, no. 98, pp. 298–305, 1973.
[20] W. N. Anderson, Jr and T. D. Morley, “Eigenvalues of the Laplacian ofa graph,” Linear and Multilinear Algebra, vol. 18, pp. 141–145, 1985.
[21] Y. Kim and M. Mesbahi, “On maximizing the second smallest eigenvalueof a state-dependent graph Laplacian,” IEEE Transactions on AutomaticControl, vol. 51, no. 1, pp. 116–120, January 2006.
[22] Y. Kim, “Bisection algorithm of increasing algebraic connectivity byadding an edge,” IEEE Transactions on Automatic Control, vol. 55, no. 1,
pp. 170–174, January 2010.
[23] M. Rafiee and A. M. Bayen, “Optimal network topology design in multiagent systems for efficient average consensus,” in Proceedings of the49th IEEE Conference on Decision and Control, December 2010, pp.
3877–3883.
[24] R. Dai and M. Mesbahi, “Optimal topology design for dynamic networks,” in Proceedings of the 50th IEEE Conference on Decision andControl and European Control Conference, December 2011, pp. 1280–
1285.
[25] C. D. Godsil and G. Royle, Algebraic graph theory. Springer New
York, 2001.
[26] F. Cuomo, A. Abbagnale, A. Cianfrani, and M. Polverini, “Keeping theconnectivity and saving the energy in the Internet,” in 2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS),
2011, pp. 319–324.
[27] F. Cuomo, A. Cianfrani, M. Polverini, and D. Mangione, “Network
pruning for energy saving in the Internet,” Computer Networks, vol. 56,
no. 10, pp. 2355–2367, 2012.
[28] K. Bilal, M. Manzano, S. Khan, E. Calle, K. Li, and A. Zomaya, “On
the characterization of the structural robustness of data center networks,”
IEEE Transactions on Cloud Computing, vol. 1, no. 1, pp. 64–77, 2013.
[29] M. J. Alenazi, E. K. Çetinkaya, and J. P. Sterbenz, “Cost-efficient
algebraic connectivity optimisation of backbone networks,” Optical
Switching and Networking, vol. 14, pp. 107–116, 2014.
[30] P. Wei, L. Chen, and D. Sun, “Algebraic connectivity maximization of an
air transportation network: The flight routes’ addition/deletion problem,”Transportation Research Part E: Logistics and Transportation Review,
vol. 61, pp. 13–27, 2014.
[31] P. Wei, G. Spiers, and D. Sun, “Algebraic connectivity maximization
for air transportation networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 15, no. 2, pp. 685–698, April 2014.
[32] J. A. Fax and R. M. Murray, “Information flow and cooperative
control of vehicle formations,” IEEE Transactions on Automatic Control,
vol. 49, no. 9, pp. 1465–1476, September 2004.

10

TABLE IL IST OF ACM GRAPHSClass

Condition

dave (= 2m)nMinimum of dave

Maximum of daveStar graph Sn

none

2
2− n

2
2− n

2
2− n

Cycle graph Cn

n≤6

2

2

2

Star graph plus one edge

n≥6

2

2

2

Star graph plus k + 1 edges (k ≥ 1)n ≥ 5k + 4

k
2+ n

1
2+ n

2k(n−k)n2n−n(for even n ≥ 10)2n1−(for odd n ≥ 11)
2
2n

11
4
− 5n
5
n
(for even n ≥ 10)2n1−(for odd n ≥ 11)22nComplete bipartite graph Kk,n−k (2 ≤ k ≤ ⌊ n
⌋)
2

2

<1
k − 2kn

TABLE IIL IST OF ACLM GRAPHSClass

Condition)
dave (= 2mnMinimum of dave

Maximum of dave

Cycle graph Cn

none

2

2

2

Complete bipartite graph Kk,n−k (2 ≤ k ≤ ⌊ n
⌋)
2

none

2k(n−k)
n

8
4− n

n
(for even n)2n1−(for odd n)
2
2n

Circulant graph with an odd number of vertices

none

d1

2

n−1

Circulant graph with an even number of vertices

Eq. (9)d12[33] L. Donetti, F. Neri, and M. A. Muñoz, “Optimal network topologies:
Expanders, Cages, Ramanujan graphs, Entangled networks and all that,”
Journal of Statistical Mechanics: Theory and Experiment, vol. 2006,
no. 08, p. P08007, August 2006.
[34] A. Bertrand and M. Moonen, “Seeing the bigger picture: How nodes
can learn their place within a complex ad hoc network topology,” IEEE
Signal Processing Magazine, vol. 30, no. 3, pp. 71–82, 2013.
[35] C. Maas, “Transportation in graphs and the admittance spectrum,”
Discrete Applied Mathematics, vol. 16, no. 1, pp. 31–49, 1987.
[36] S. M. Fallat and S. Kirkland, “Extremizing algebraic connectivity subject
to graph theoretic constraints,” The Electronic Journal of Linear Algebra,
vol. 3, pp. 48–74, April 1998.
[37] S. Belhaiza, N. M. M. de Abreu, P. Hansen, and C. S. Oliveira,“Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity,” in Graph Theory and Combinatorial Optimization,
O. Marcotte, D. Avis, and A. Hertz, Eds. Springer, 2005, pp. 1–16.
[38] A. Ghosh and S. Boyd, “Upper bounds on algebraic connectivity via
convex optimization,” Linear algebra and its applications, vol. 418,
no. 2, pp. 693–707, 2006.
[39] ——, “Growing well-connected graphs,” in Proceedings of the 45th
IEEE Conference on Decision & Control, December 2006, pp. 6605–
6611.
[40] N. M. M. de Abreu, “Old and new results on algebraic connectivity ofgraphs,” Linear algebra and its applications, vol. 423, no. 1, pp. 53–73,
May 2007.
[41] D. Mosk-Aoyama, “Maximum algebraic connectivity augmentation is
NP-hard,” Operations Research Letters, vol. 36, pp. 677–679, 2008.
[42] H. Wang and P. Van Mieghem, “Algebraic connectivity optimization via
link addition,” in Proceedings of the 3rd International Conference on
Bio-Inspired Models of Network, Information and Computing Sytems,
2008, pp. 1–8.
[43] H. Wang, R. Kooij, and P. Van Mieghem, “Graphs with given diameter
maximizing the algebraic connectivity,” Linear Algebra and its Applications, vol. 433, pp. 1889–1908, 2010.
[44] P. Van Mieghem, Graph Spectra for Complex Networks. Cambridge
University Press, 2011.
[45] T. Bıyıkoğlu and J. Leydold, “Graphs of given order and size andminimum algebraic connectivity,” Linear Algebra and its Applications,vol. 436, no. 7, pp. 2067–2077, 2012.
[46] A. Sydney, C. Scoglio, and D. Gruenbacher, “Optimizing algebraic
connectivity by edge rewiring,” Applied Mathematics and Computation,
vol. 219, pp. 5465–5479, 2013.
[47] T. Kolokolnikov, “Maximizing algebraic connectivity for certain
families of graphs,” 2013, preprint. [Online]. Available: http://www.
mathstat.dal.ca/∼tkolokol/papers/maxalg.pdf

n − 1 (for n mod 4 = 0)n − 2 (for n mod 4 ̸= 0)[48] B. Mohar, “The Laplacian spectrum of graphs,” in Graph Theory,
Combinatorics and Applications, Y. Alavi, G. Chartrand, O. Ollermann,and A. Schwenk, Eds. New York: Wiley, 1991, pp. 871–898.