2016 International Symposium on Nonlinear Theory and Its Applications,
NOLTA2016, Yugawara, Japan, November 27th-30th, 2016

Extensions of a Theorem on Algebraic Connectivity Maximizing Graphs
Ryoya Ishii and Norikazu Takahashi
Graduate School of Natural Science and Technology, Okayama University
3–1–1 Tsushima-naka, Kita-ku, Okayama, 700–8530 Japan
Email: ishii@momo.cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—The second smallest eigenvalue of the Laplacian matrix of a graph, also known as the algebraic connectivity, is an important measure that represents how strongly
the graph is connected. The algebraic connectivity alsocharacterizes the performance of some dynamic processeson networks such as consensus in multiagent networks andsynchronization of coupled oscillators. In this paper, westudy the problem of finding graphs that maximize the algebraic connectivity among all graphs with the same number of vertices and edges, and extend a known result aboutcomplete bipartite graphs to complete multipartite graphs.
1. Introduction
Algebraic connectivity [1] of a graph, which is definedas the second smallest eigenvalue of the Laplacian matrix,is an important measure that represents how strongly thegraph is connected. Not only it has been intensively studied in mathematics [2, 3, 4], but also it has attracted a great
deal of attention from researchers in engineering. For example, the convergence rate of a well-known consensus algorithm for multiagent networks is determined by the algebraic connectivity of the network [5]. Also, the algebraic
connectivity plays important roles in the design of computer networks [6] and air transportation networks [7].
Recently, Ogiwara et al. [8] studied the problem of finding graphs with a given number of vertices and edges thatmaximize the algebraic connectivity. This problem is important from various perspectives such as the fast convergence of the consensus algorithm, the robustness of networks against failures and attacks, and so on. They provedthat some well-known classes of graphs such as star graphs,
cycle graphs and complete bipartite graphs are algebraic
connectivity maximizers under certain conditions. This
problem was also considered by Kolokolnikov [9]. He presented a conjecture that the complete bipartite graph K2,n−2
maximizes the algebraic connectivity among all graphswith n vertices and 2(n − 2) edges. He also showed byexhaustive search that this conjecture holds true for all nless than or equal to 13. Fujihara and Takahashi [10] studied a slightly diﬀerent problem and proved that any complete multipartite graph maximizes the algebraic connectivity among all graphs with the same degree matrix.
In this paper, we prove that if a complete multipartite
graph satisfies a certain condition then it maximizes the algebraic connectivity among all graphs with the same num-

ber of vertices and edges. This is an extension of a theorem
given by Ogiwara et al. [8], which states that any complete
bipartite graph Kn1 ,n2 with n1 ≈ n2 maximizes the algebraic
connectivity among all graphs with n1 +n2 vertices and n1 n2
edges. We further generalize this result to graphs obtained
from complete multipartite graphs by adding some edges.
2. Algebraic Connectivity Maximizing Graphs
2.1. Notations and Definitions
Throughout this paper, by a graph we mean a simple
undirected graph. Let G = (V(G), E(G)) be a graph withthe vertex set V(G) = {1, 2, . . . , n} and the edge set E(G).
The Laplacian matrix of G is defined by L(G) = D(G) −A(G) [1] where D(G) = diag(d1 (G), d2 (G), . . . , dn (G)) is
the degree matrix and A(G) = (ai j (G)) ∈ {0, 1}n×n is the adjacency matrix. Because L(G) is positive semi-definite, its
eigenvalues, which are denoted by λ1 (G), λ2 (G), . . . , λn (G),are nonnegative real numbers. In the remainder of this paper, we assume without loss of generality that 0 ≤ λ1 (G) ≤λ2 (G) ≤ · · · ≤ λn (G). Because the Laplacian matrix satisfies L(G)1 = 0 = 0 · 1 where 1 is the vector of all ones and
0 is the zero vector, the smallest eigenvalue λ1 (G) is 0 and 1
is an eigenvector associated with λ1 (G). The second smallest eigenvalue λ2 (G) is called the algebraic connectivity [1]of G. It represents how strongly the graph is connected. In
particular, λ2 (G) is positive if and only if G is connected.
The algebraic connectivity maximizing graph is defined
as follows [8].
Definition 1 Let Gn,m be the set of all graphs with n vertices and m edges. If a graph G ∈ Gn,m satisfies the condition that∀G′ ∈ Gn,m , λ2 (G) ≥ λ2 (G′ )then G is called an algebraic connectivity maximizing
graph in Gn,m .
2.2. Known Results
If the vertex set V(G) = {1, 2, . . . , n} of a graph G ispartitioned into k (≥ 2) subsets V1 , V2 , . . . , Vk in such a waythat vertices i ∈ Va and j ∈ Vb are adjacent to each other
if and only if a , b, then G is called a complete k-partite
graph and denoted by Kn1 ,n2 ,...,nk where nl = |Vl | for l =1, 2, . . . , k. An example of such a graph is shown in Fig. 1.

- 598 -

where I is the identity matrix. From (2) and (3) we haveL(Kn1 ,n2 ,...,nk )v = (n − λ)v
which means that n − λ is an eigenvalue of L(Kn1 ,n2 ,...,nk )and v is an eigenvector associated with n − λ. In addition, it is easy to see that the dimension of the eigenspaceof L(Knc1 ,n2 ,...,nk ) associated with λ is equal to that of□L(Kn1 ,n2 ,...,nk ) associated with n − λ.
Figure 1: Complete 4-partite graph K1,1,2,4 .
In the following discussions, we assume without loss ofgenerality that1 ≤ n1 ≤ n2 ≤ · · · ≤ nk .

(1)

The complete n-partite graph K1,1,...,1 is called the completegraph and denoted by Kn in this paper.
First, we present some fundamental results about the
eigenvalues of the Laplacian matrix and their multiplicities.

Theorem 2 may not be new. However, it is diﬃcult tofind this result in the existing literature. We therefore haveprovided a proof of it.
Next, we present two results given by Ogiwara et al. [8]about the suﬃcient condition for a complete bipartite graphto be an algebraic connectivity maximizing graph.
Theorem 3 ([8]) If k = 2 and two positive integers n1 andn2 satisfy n1 + n2 ≥ 3 and
n1 −

2n21
<1
n1 + n2

Lemma 1 ([2]) The eigenvalues of L(Kn ) are 0, with multiplicity 1, and n, with multiplicity n − 1.

as well as (1) then the complete bipartite graph Kn1 ,n2 is analgebraic connectivity maximizing graph in Gn1 +n2 ,n1 n2 .

Theorem 1 ([2]) If λ is an eigenvalue of L(G) then 0 ≤λ ≤ n. The multiplicity of 0 equals the number of connected components of G. The multiplicity of n equals one
less than the number of connected components of Gc , thecomplement of G.

Corollary 1 ([8]) If k = 2 and two positive integers n1 andn2 satisfy n1 + n2 ≥ 3 and⌊⌋⌊n + n ⌋n1 + n2 − 1
1
2≤ n1 ≤
2
2

Theorem 2 The eigenvalues of L(Kn1 ,n2 ,...,nk ) are 0, n −nk , n−nk−1 , . . . , n−n1 and n, with multiplicity 1, nk −1, nk−1 −1, . . . , n1 − 1 and k − 1, respectively.

as well as (1) then the complete bipartite graph Kn1 ,n2 is analgebraic connectivity maximizing graph in Gn1 +n2 ,n1 n2 .

Proof: Because Kn1 ,n2 ,...,nk is connected, it follows from
Theorem 1 that the smallest eigenvalue 0 of L(Kn1 ,n2 ,...,nk )has multiplicity 1. Also, because the complement Knc1 ,n2 ,...,nkof Kn1 ,n2 ,...,nk has k connected components which are isomorphic to Kn1 , Kn2 , . . . , Knk , it follows from Theorem 1
that L(Kn1 ,n2 ,...,nk ) has the largest eigenvalue n with multiplicity k − 1. Moreover, we see from Lemma 1 that the
eigenvalues of L(Knc1 ,n2 ,...,nk ) are 0, n1 , n2 , . . . , nk with multiplicity k, n1 − 1, n2 − 1, . . . , nk − 1, respectively. Hence,in order to complete the proof, we only have to show that
if L(Knc1 ,n2 ,...,nk ) has an eigenvalue λ other than 0 and n withmultiplicity µ then L(Kn1 ,n2 ,...,nk ) has an eigenvalue n − λwith the same multiplicity.
Note that Kn1 ,n2 ,...,nk and Knc1 ,n2 ,...,nk satisfy
L(Kn1 ,n2 ,...,nk ) = L(Kn ) − L(Knc1 ,n2 ,...,nk ) .

(2)

Let v be an eigenvector of L(Knc1 ,n2 ,...,nk ) associated with λ.
Then v is orthogonal to 1. Multiplying both sides of (2) byv from right, we have()
(L(Kn ) − L(Knc1 ,n2 ,...,nk ))v = nI − 11T v − λv==nv − λv(n − λ)v(3)

We also provide two well-known results about the algebraic connectivity, that will be needed in later discussions.
Theorem 4 ([1]) If G is not a complete graph then λ2 (G) ≤δ(G) where δ(G) = min1≤i≤n {di (G)}.
Theorem 5 ([3]) Let G′ ∈ Gn,m+1 be a graph obtained byadding an edge to G ∈ Gn,m . Then we have
λ1 (G) ≤ λ1 (G′ ) ≤ λ2 (G) ≤ λ2 (G′ ) ≤ · · · ≤ λn (G) ≤ λn (G′ ) .
3. Exhaustive Search of Algebraic Connectivity Maximizing Graphs
In order to see what kind of complete multipartite graphs
can be algebraic connectivity maximizing graphs, we developed an exhaustive search algorithm based on the graphenumeration algorithm proposed by Sato and Nakano [11]and applied it to Gn,m for various values of (n, m).
We first applied the algorithm to Gn,m with n ≤ 10 suchthat it contains a complete bipartite graph. For n = 10, forexample, the algorithm was applied to G10,9 , G10,16 , G10,21 ,G10,24 and G10,25 . As a result, it was found that any bipartite
graph Kn1 ,n2 with n1 + n2 ≤ 10 is an algebraic connectivity
maximizing graph in Gn1 +n2 ,n1 n2 .

- 599 -

1

2

3

4

5
6

7

Figure 2: An algebraic connectivity maximizing graph in
G7,14 .

Figure 4: An algebraic connectivity maximizing graphfound by the exhaustive search algorithm for G9,28 .
an algebraic connectivity maximizing graph in Gn,m where∑∑n = kl=1 nl and m = kl=1 nl (n − nl )/2.

Figure 3: An algebraic connectivity maximizing graphfound by the exhaustive search algorithm for G8,17
Next we applied the algorithm to Gn,m such that a complete tripartite graph is contained in it. First let us consider
G7,14 which contains K1,2,4 . An algebraic connectivity maximizing graph found by the algorithm is shown in Fig. 2.
Note that it is not a complete multipartite graph. Moreover,
all other graphs found by the algorithm were isomorphic to
the graph in Fig. 2. This means that K1,2,4 is not an algebraic connectivity maximizing graph. On the other hand,for G8,24 and G9,27 , the algorithm found K2,2,2,2 and K3,3,3,3 ,respectively, as algebraic connectivity maximizing graphs.
From these results and Corollary 1, it is conjectured that thecomplete k-partite graph Kn1 ,n2 ,...,nk with n1 = n2 = · · · = nk
is an algebraic connectivity maximizing graph. It is provedin the next section that the conjecture is in fact true.
We also applied the algorithm to Gn,m which does notnecessarily contain a complete multipartite graph. An algebraic connectivity maximizing graph found for G8,17 isshown in Fig. 3 and that for G9,28 is shown in Fig. 4. It iseasily seen that each of them is obtained from a complete
multipartite graph Kn1 ,n2 ,...,nk with n1 = n2 = · · · = nk byadding one edge. It is proved in the next section that thesegraphs are algebraic connectivity maximizing graphs.

Proof: By Theorem 2, the algebraic connectivity of thecomplete k-partite graph Kn1 ,n2 ,...,nk is equal to n − nk . We
therefore prove under the assumption (4) that λ2 (G) ≤ n−nk∑∑
for all G ∈ Gn,m where n = kl=1 nl and m = kl=1 nl (n −nl )/2. Furthermore, by Theorem 4, it suﬃces for us to show
under the assumption (4) that δ(G) ≤ n − nk for all G ∈Gn,m (note that G is not a complete graph because of theassumption nk ≥ 2). The sum of the degrees of all vertices
of G is given byn∑di (G) = 2m =

i=1

k
∑

nl (n − nl ) = n2 −

k
∑

l=1

n2l .

l=1

Here it follows from assumption (4) that−k∑n2l = −

l=1

k−1
∑

n2l − n2k ≤ −nk

l=1

k−1
∑

nl − n2k = −nnkl=1

from which we haven∑di (G) ≤ n2 − nnk = n(n − nk ).
i=1

Therefore, we finally have1∑di (G) = n − nkn i=1nδ(G) ≤

which completes the proof.

□

4. Theoretical Analysis

Lemma 3 Let k be any integer greater than or equal to 2.
Positive integers n1 , n2 , . . . , nk satisfy (1) and (4) if and only
if n1 = n2 = · · · = nk ≥ 2.

We give two theorems that can be considered as extensions of Theorem 3 and Corollary 1. Before doing so, we
present two lemmas.

Proof: It follows from (1) that nk nl ≥ n2l for l = 1, 2,. . . , k − 1. Hence (4) holds if and only if 2nl ≤ nk nl = n2l
for l = 1, 2, . . . , k − 1, that is, n1 = n2 = · · · = nk ≥ 2. □Lemma 2 If k ≥ 2 and k positive integers n1 , n2 , . . . , nksatisfyk−1
k−1∑∑
nk ≥ 2 and nk
nl ≤
n2l
(4)

From Lemmas 2 and 3, we immediately obtain the following theorem.

l=1

l=1

as well as (1) then the complete k-partite graph Kn1 ,n2 ,...,nk is

Theorem 6 If k ≥ 2, the positive integers n1 , n2 , . . . , nk areequal to each other, and n1 ≥ 2 then the complete k-partite
graph Kn1 ,n2 ,...,nk is an algebraic connectivity maximizing
graph in Gn,m where n = kn1 and m = kn1 (n − n1 )/2.

- 600 -

This theorem can be further extended as follows.

Acknowledgement

Theorem 7 If k ≥ 2, the positive integers n1 , n2 , . . . , nk areequal to each other, n1 ≥ 2, and p is a positive integer
less than kn1 /2 then any graph obtained from the complete
k-partite graph Kn1 ,n2 ,...,nk by adding p edges has the same
algebraic connectivity as Kn1 ,n2 ,...,nk and is an algebraic connectivity maximizing graph in Gn,m+p where n = kn1 andm = n(n − n1 )/2.
Proof: Suppose that k, n1 , n2 , . . . , nk and p satisfy the assumptions of the statement. We first show thatp ≤ k(n1 − 1) − 1.
If kn1 is even then we havek(n1 − 1) − 1 − p ≥
=

(5)
(

k(n1 − 1) − 1 −

)
kn1
−1
2

=

References[1] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Mathematical Journal, vol. 23, no. 98,
pp. 298–305, 1973.
[2] W. N. Anderson Jr. and T. D. Morley, “Eigenvalues of
the Laplacian of a graph,” Linear and Multilinear Algebra, vol. 18, pp. 141–145, 1985.
[3] B. Mohar, “The Laplacian spectrum of graphs,” inGraph Theory, Combinatorics, and Applications, Y.
Alavi et al. Eds., pp. 871–898, 1991.

k(n1 − 2)
2[4] C. Godsil and G. Royle, Algebraic Graph Theory,
Springer New York, 2001.

which is nonnegative. If kn1 is odd then we havek(n1 − 1) − 1 − p ≥This work was partially supported by JSPS KAKENHI
Grant Number JP15K00035.

[5] R. Olfati-Saber, J. A. Fax and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. of the IEEE, vol. 95, no. 1, pp. 215–233,
January 2007.

kn1 − 1k(n1 − 1) − 1 −2
k(n1 − 2) − 12which is positive because k ≥ 3 and n1 ≥ 3. Therefore, palways satisfies (5). Let G∗ be any graph obtained from thecomplete k-partite graph Kn1 ,n1 ,...,n1 by adding p edges. The
eigenvalues of L(Kn1 ,n1 ,...,n1 ) are 0 with multiplicity 1, n−n1with multiplicity k(n1 − 1), and n with multiplicity k − 1 dueto Theorem 2. By this fact, together with Theorem 5 and(5), we have λ2 (G∗ ) = n − n1 = λ2 (Kn1 ,n2 ,...,nk ). In order toprove the second part, it suﬃces to show that λ2 (G) ≤ n−n1
for any G ∈ Gn,m+p . By Theorem 4, we have[6] M. J. F. Alenazi, E. K. Çetinkaya and J. P. G. Sterbenz,“Cost-eﬃcient algebraic connectivity optimisation of
backbone networks,” Optical Switching and Networking, vol. 14, pp. 107–116, 2014.

1∑
2(m + p)λ2 (G) ≤ δ(G) ≤di (G) =n i=1n[8] K. Ogiwara, T. Fukami and N. Takahashi, “Maximizing algebraic connectivity in the space of graphs with
fixed number of vertices and edges,” to appear in IEEE
Trans. on Control of Network Systems.

n

(6)

where
2(m + p) n(n − n1 ) + 2p
2p=
= n − n1 +nnn
and 2p/n is less than 1 from the assumption. Therefore, theinequality (6) implies that λ2 (G) ≤ n − n1 .
□5. Conclusion
In this paper, we first proved that any complete multipartite graph Kn1 ,n2 ,...,nk with n1 = n2 = · · · = nk is an algebraic connectivity maximizing graph. We then extended
this result to graphs obtained from such complete multipartite graphs by adding some edges. However, we have to saythat these results are rather severe, because Theorems 6 or
7 apply to the set of graphs with n vertices and m edges for
relatively few choices of n and m. A future problem is toobtain milder suﬃcient conditions.

[7] P. Wei, G. Spiers and D. Sun, “Algebraic connectivity
maximization for air transportation networks,” IEEE
Trans. on Intelligent Transportation Systems, vol. 15,
no. 2, pp. 685–698, April 2014.

[9] T. Kolokolnikov, “Maximizing algebraic connectivity
for certain families of graphs,” Linear Algebra and its
Applications, vol.471, pp.122–140, 2015.
[10] T. Fujihara and N. Takahashi, “Maximality of the algebraic connectivity of complete multipartite graphs
and a 2-switch-based method for finding algebraic connectivity locally maximizing graphs,” IEICE Technical
Report, vol.115, no.442, pp.31–36, January 2016 (inJapanese).
[11] K. Sato and S. Nakano, “Enumeration of graphswith a specified degree sequence,” IEICE Trans. on
Fundamentals of Electronics, Communications andComputer Science (Japanese Edition), vol. 91, no. 7,
pp. 716–725, July 2008 (in Japanese).

- 601 -