2014 International Symposium on Nonlinear Theory and its Applications
NOLTA2014, Luzern, Switzerland, September 14-18, 2014

On Graphs that Locally Maximize Algebraic Connectivity in the Space ofGraphs with the Fixed Degree Sequence
Takuro Fujihara† and Norikazu Takahashi†† Graduate School of Natural Science and Technology, Okayama University
3–1–1 Tsushima-naka, Kita-ku, Okayama 700–8530, Japan
Email: fujihara@momo.cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, isan important measure that characterizes the performanceof some dynamic processes on the network. In this paper,
we study the problem of finding graphs that locally maximize the algebraic connectivity in the space of graphs withthe fixed degree sequence. We first prove that complete bipartite graphs are such graphs. We next find some 3-regulargraphs that locally maximize the algebraic connectivity byusing a local search algorithm based on 2-switch.

In this paper, we consider the problem of finding graphsthat locally maximize the algebraic connectivity in thespace of graphs with the fixed degree sequence. Note that
this problem setting diﬀers from those works mentioned
above. We first introduce definitions of the algebraic connectivity maximizing (ACM) graphs and the algebraic connectivity locally maximizing (ACLM) graphs. We thenprove that complete bipartite graphs are ACLM graphs. We
finally propose a local search algorithm based on 2-switch
to find ACLM graphs, and apply it to 3-regular graphs.
2. Algebraic Connectivity Locally Maximizing Graph

1. Introduction

Throughout this paper, by a graph, we mean a simple
undirected graph. Let G = (V(G), E(G)) be a graph composed of n vertices and m edges, where V(G) = {1, 2, . . . , n}is the vertex set and E(G) = {e1 , e2 , . . . , em } is the edge set.
Each edge is expressed as an unordered pair of two distinct
vertices like {i, j}. The matrix A(G) = (ai j (G)) defined by

The algebraic connectivity of a network is defined as thesecond smallest eigenvalue of the Laplacian matrix of the
network [1]. It is well known that the performance of somedynamic processes on the network is characterized by thealgebraic connectivity [2]. For example, the convergence
rate of the consensus algorithm proposed by Olfati-Saberand Murray [3] for multiagent networks is determined by
the algebraic connectivity: the larger the algebraic connectivity is, the faster the consensus algorithm converges. The
algebraic connectivity is also an important measure that determines the robustness of networks.
Finding graphs that maximize the algebraic connectivity
under certain conditions is a fundamental problem not only
from a theoretical but also from a practical point of view.
In fact, this problem has recently been studied extensively
in various fields from mathematics to engineering [4–7].
Wang et al. [4] focused their attention on graphs composedof a chain of some cliques, and proved under some assumptions that these graphs maximize the algebraic connectivity
in the set of graphs with the given diameter. Ogiwara etal. [5] identified some classes of graphs that maximize or
locally maximize the algebraic connectivity when the number of vertices and edges are given. Dai and Mesbahi [6]considered the optimal topology design problem for dynamic networks in three diﬀerent scenarios, and formulated
these problems as mathematical programming problems.
Sydney [7] proposed algorithms for rewiring edges in order to maximally increase the algebraic connectivity.

Let λ1 (G), λ2 (G), . . . , λn (G) be eigenvalues of L(G). Because L(G) is symmetric, these eigenvalues are all real.
We thus assume without loss of generality that λ1 (G) ≤λ2 (G) ≤ · · · ≤ λn (G). Also, because L(G) is diagonallydominant, all eigenvalues are nonnegative. Furthermore,because L(G)1 = 0 holds, where 1 and 0 are the vectorsof all ones and all zeros, respectively, 0 is an eigenvalue of
L(G). From these observations, we have λ1 (G) = 0.
The algebraic connectivity [1] is defined as follows.

This work was partially supported by KAKENHI 24560076 and23310104.

Definition 1 The algebraic connectivity of a graph G is thesecond smallest eigenvalue λ2 (G) of L(G).

{ai j (G) =1, if {i, j} ∈ E(G),0, otherwise,

is called the adjacent matrix of G. The diagonal matrix
D(G) = diag(d1 (G), d2 (G), . . . , dn (G)) defined by
di (G) = |{ j | {i, j} ∈ E(G)}|is called the degree matrix of G. The Laplacian matrix L(G)of G is then defined in terms of A(G) and D(G) as
L(G) = D(G) − A(G) .

- 353 -

Figure 1: 2-switch. Each dotted line means that there may
or may not exist an edge.
Suppose that a graph G = (V(G), E(G)) has four distinct
vertices such that {i, j} ∈ E(G), {k, l} ∈ E(G), {i, k} < E(G)and { j, l} < E(G). Let G′ = (V(G′ ), E(G′ )) be the graph obtained from G by removing two edges {i, j} and {k, l}, andby adding two new edges {i, k} and { j, l} (see Fig. 1). Thistransformation is called 2-switch. It is clear that the degree
matrix does not change before and after the application of
a 2-switch. Moreover, it is well known that, for any pair ofgraphs G and G′ such that D(G) = D(G′ ), G can be transformed into G′ by applying 2-switches sequentially [8].
Let us now give two definitions for those graphs thatmaximize or locally maximize the algebraic connectivity.
Definition 2 A graph G is called an algebraic connectivity
maximizing (ACM) graph in GD(G) if′∀G ∈ GD(G) ,λ2 (G1 ) ≤ λ2 (Ka,n−a ) ≤ λ3 (G1 ) ≤ λ3 (Ka,n−a ) ≤ λ4 (G1 ) ≤ λ4 ,λ3 (G1 ) ≤ λ3 (G2 ) ≤ λ4 (G1 ) ,λ3 (G3 ) ≤ λ3 (G2 ) ≤ λ4 (G3 ) ,λ2 (G) ≤ λ3 (G3 ) ≤ λ3 (G) ≤ λ4 (G3 ) ≤ λ4 (G) .
From these inequalities, we have
λ2 (G) ≤ λ3 (G3 ) ≤ λ3 (G2 ) ≤ λ4 (G1 ) ≤ λ4 (Ka,n−a ) .
λ2 (Ka,n−a ) = · · · = λn−a (Ka,n−a ) = a
as shown in [10]. Moreover, because n ≥ 6 and (1) hold,we have
λ4 (Ka,n−a ) = λ2 (Ka,n−a ) .
(3)
It follows from (2) and (3) thatλ2 (G) ≥ λ2 (G ) ,λ2 (G) ≤ λ4 (Ka,n−a ) = λ2 (Ka,n−a ) .

Definition 3 A graph G is called an algebraic connectivity
locally maximizing (ACLM) graph in GD(G) if
λ2 (G) ≥ λ2 (G′ ) ,where GD(G) is same as Definition 2, and ND(G) (G) is theset of all graphs obtained from G by applying a single 2switch.
It is apparent from these definitions that if a graph G isan ACM graph in GD(G) then G is an ACLM graph in GD(G) .
However, the converse is not true.
3. Complete Bipartite Graphs
We first consider whether the complete bipartite graphKa,n−a is an ACLM graph in GD(Ka,n−a ) .
Theorem 1 Let n be any integer greater than or equal tosix. Let a be any integer such that2 ≤ a ≤ ⌊n/2⌋(2)

Because a ≤ n/2, the eigenvalues of L(Ka,n−a ) satisfies′

where GD(G) is the set of all graphs having the same degree
matrix as G.

∀G′ ∈ ND(G) (G),Proof Let G be any graph in ND(Ka,n−a ) (Ka,n−a ). We assume
without loss of generality that G is obtained from Ka,n−a byremoving edges {1, a + 1} and {2, a + 2} and adding edges{1, 2} and {a + 1, a + 2}. Let G1 be the graph obtained from
Ka,n−a by removing the edge {1, a + 1}. Let G2 be the graphobtained from G1 by adding the edge {1, 2}. Let G3 be thegraph obtained from G2 by removing the edge {2, a + 2}.
Then G is the graph obtained from G3 by adding the edge
{a + 1, a + 2}. By the interlace theorem [9], we have thefollowing inequalities:(1)

where ⌊n/2⌋ denotes the largest integer less than or equal ton/2. Then the complete bipartite graph Ka,n−a is an ACLM
graph in GD(Ka,n−a ) .

This means that Ka,n−a is an ACLM graph in GD(Ka,n−a ) because G is any member of ND(Ka,n−a ) (Ka,n−a ).
□Although Theorem 1 says that complete bipartite graphs
are ACLM graphs if the number of vertices is not less thansix, it is not clear whether the algebraic connectivity of
Ka,n−a with n ≥ 6 and (1) is strictly greater than that ofany graph in ND(Ka,n−a ) (Ka,n−a ). The following theorem addresses this issue.
Theorem 2 Let n and a be the same as in Theorem 1. For
any graph G ∈ ND(Ka,n−a ) (Ka,n−a ), we have2
1
≤ λ2 (Ka,n−a ) − .
n−a3
Proof We assume without loss of generality that G is thegraph obtained from Ka,n−a by removing edges {1, a + 1}
and {2, a + 2} and adding edges {1, 2} and {a + 1, a + 2}.
Then the Laplacian matrix of G is given by
λ2 (G) ≤ λ2 (Ka,n−a ) − 1 +L(G) = L(Ka,n−a ) − M
where M = (mi j ) is given by1,
if (i, j) = (1, 2), (2, 1),





(a + 1, a + 2), (a + 2, a + 1) ,



−1,
if
(i,
j) = (1, a + 1), (a + 1, 1),
mi j = 




(2,
a + 2), (a + 2, 2) ,



 0,
otherwise .

- 354 -

Since λ2 (G) is expressed as
λ2 (G) =min

4. Local Search Algorithm for Finding ACLM Graphs

xT 1=0, ∥x∥=1

xT L(G)x ,In this section, we consider the problem of finding an
ACLM graph in GD(G0 ) for a given G0 . Because it is very
diﬃcult to solve this problem analytically, we use a simple
2-switch-based local search algorithm described below.

we can find an upper bound for λ2 (G) as
λ2 (G) ≤ v T L(G)v(4)

where v is any vector satisfying v T 1 = 0 and ∥v∥ = 1.
Let us consider the case where v is set to an eigenvectorof Ka,n−a associated with λ2 (Ka,n−a ) = a. By solving theequation L(Ka,n−a )v = av, we havea∑vi = 0 and

i=1

n
∑

vi = 0(5)i=a+1

if a = n/2, andv1 = v2 = · · · = va = 0 andn∑vi = 0(6)

i=a+1

if a < n/2. Because (6) implies (5), we assume hereafterthat v satisfies (6) as well as ∥v∥ = 1. Then the right-handside of (4) can be expressed asv T L(G)v= v T (L(Ka,n−a ) − M)v= λ2 (Ka,n−a ) − v T Mv
= λ2 (Ka,n−a ) − 2va+1 va+2 .

We now consider the problem of minimizing the second
term subject to (6) and ∥v∥ = 1. This problem is formulated
as the optimization problem:
minimize −2va+1 va+2∑nsubject tovi = 0 ,∑i=a+1n2v
i=a+1 i = 1 .

(7)

Using the method of Lagrange multiplier, we obtain an optimal solution of (7) which is given by{ µ1, if i = a + 1, a + 2 ,2)v∗i = 2(1−µ(8)µ1− 2µ2 ,
if i = a + 3, a + 4, . . . , n
where

√
µ1 =

8(n − a − 2),(n − a)3

µ2 =

n−a−2
.
n−a

Substituting (8) to the objective function of (7) and using
the assumptions on n and a, we have−2v∗a+1 v∗a+2=≤−1 + 2/(n − a)−1 + 4/n (∵ a ≤ n/2)≤=

−1 + 2/3−1/3

which completes the proof.

(∵ n ≥ 6)□

Algorithm 1 Given a graph G0 , the following algorithm
returns an ACLM graph G ∈ GD(G0 ) .
1. Set t ← 0.
2. Set (i, j, k, l) ← (1, 2, 3, 4).
3. If 2-switch is applicable to four vertices i, j, k and l,that is, if {i, j} ∈ E(Gt ), {k, l} ∈ E(Gt ), {i, k} < E(Gt )and { j, l} < E(Gt ) are satisfied then go to Step 4. Otherwise, go to Step 5.
4. Apply 2-switch to four vertices i, j, k and l of Gt to
get G′t . If λ2 (G′t ) > λ2 (Gt ) then set Gt+1 ← G′t andt ← t + 1 and go to Step 2. Otherwise, go to Step 5.
5. If (i, j, k, l) = (n − 3, n − 2, n − 1, n) then return Gt andstop. Otherwise, update (i, j, k, l) in ascending lexicographic order and go to Step 3.
Note that the variable (i, j, k, l) is reset to the initial value(1, 2, 3, 4) as soon as a graph G′t such that λ2 (G′t ) > λ2 (Gt )is found. Therefore, this algorithm stops only when no such
G′t which means that the output is an ACLM graph.
Although Algorithm 1 can be applied to any graph, we
hereafter focus our attention on 3-regular graphs. In multiagent networks, it is very natural to assume that all agents
have the same communication capability. Because the degree of each vertex representing an agent can be consideredas the communication capability of the agent, 3-regulargraphs correspond to the simplest case in which every agent
can interact with three other agents.
For each n ∈ {8, 10, . . . , 22}, we choose a 3-regular graphwith n vertices as the initial graph G0 and apply Algorithm 1 to obtain an ACLM graph in GD(G0 ) . Apparently,
how to choose the initial graph G0 is an important issue. In
our experiment, we set G0 to the circulant graph such thatthe first row of the adjacency matrix A(G0 ) = (ai j (G0 )) is
given by{1, if j = 2, n2 + 1, n ,a1 j (G0 ) =0, otherwise .
For n = 6, the circulant graph having this kind of adjacentmatrix is the bipartite graph K3,3 which is an ACLM graphin GD(K3,3 ) as proved by Theorem 1. So the algebraic connectivity of the circulant graph is expected to be high.
ACLM graphs obtained by Algorithm 1 are shown in
Fig. 2. First of all, we should note that in all cases except(a) the obtained graph diﬀers from the initial one. Thismeans that the circulant graph used for the initial graph is
not an ACLM graph in general. Second, we have to say- 355 -

that it is diﬃcult to find common features for all graphs.
Further investigation is needed to better understand ACLM
graphs in 3-regular graphs.

(a) n = 8(b) n = 10(c) n = 12(d) n = 14

Table 1: Algebraic connectivities of the initial and final
graphs. For each n, G0 and G∞ represent the initial andfinal graph, respectively.
n
8
10
12
14
16
18
20
22

λ2 (G0 )2
1.381966
10.7530204
0.5857864
0.4679111
0.2266939
0.1920181

λ2 (G∞ )2
2
1.4679111
1.2891708
1.1729091
1.0303845
0.8299135
0.7406081

λ2 (G∞ )/λ2 (G0 )11.4472136
1.4679111
1.7119998
2.0022812
2.2020946
3.6609432
3.8569703

pp. 298–305, 1973.
[2] M. Mesbahi and M. Egerstedt, Graph Theoretic
Methods in Multiagent Networks. Princeton: Princeton University Press, 2010.

(e) n = 16

[3] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networks of dynamic agents,” in Proceedingsof the 2003 American Control Conference, pp. 951–
956, June 2003.

(f) n = 18(g) n = 20

[4] H. Wang, R. Kooij, and P. Van Mieghem, “Graphswith given diameter maximizing the algebraic connectivity,” Linear Algebra and its Applications,vol. 433, pp. 1889–1908, 2010.

(h) n = 22

Figure 2: ACLM graphs obtained by Algorithm 1.
The values of the algebraic connectivities of the initialgraph, denoted by G0 , and the final graph, denoted by G∞ ,are shown in Table 1. For all cases except (a), the algebraic
connectivity was increased through the local search by afactor greater than 1.4. In addition, the factor is monotone
increasing with the number of vertices.
5. Conclusion
The problem of finding graphs that maximize the algebraic connectivity in the space of graphs with the fixed
degree sequence has been studied in this paper. First, wehave proved that complete bipartite graphs have this property. Next, we have presented a local search algorithm
based on 2-switch to find graphs with the same property
and applied to 3-regular graphs. Further investigation on
3-regular graphs is a future problem.
References[1] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Mathematical Journal, vol. 23, no. 98,[5] K. Ogiwara and N. Takahashi, “On topology of networked multi-agent systems for fast consensus,” inProceedings of 2011 International Symposium on
Nonlinear Theory and its Applications, pp. 56–59,
September 2011.
[6] R. Dai and M. Mesbahi, “Optimal topology design for
dynamic networks,” in Proceedings of the 50th IEEE
Conference on Decision and Control and European
Control Conference, pp. 1280–1285, December 2011.
[7] A. Sydney, C. Scoglio, and D. Gruenbacher, “Optimizing algebraic connectivity by edge rewiring,”
Applied Mathematics and Computation, vol. 219,
pp. 5465–5479, 2013.
[8] S. Bereg and H. Ito, “Transforming graphs with thesame degree sequence,” in Computational Geometry
and Graph Theory, pp. 25–32, Springer, 2008.
[9] C. D. Godsil, G. Royle, and C. Godsil, Algebraic
graph theory. Springer New York, 2001.
[10] W. N. Anderson, Jr and T. D. Morley, “Eigenvaluesof the Laplacian of a graph,” Linear and Multilinear
Algebra, vol. 18, pp. 141–145, 1985.

- 356 -