2015 International Symposium on Nonlinear Theory and its Applications
NOLTA2015, Kowloon, Hong Kong, China, December 1-4, 2015

Complete Multipartite Graphs Maximize Algebraic Connectivity
in the Neighborhood based on 2-Switch
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, is an
important quantity for various network systems because it
indicates how well the network is connected. The algebraic
connectivity also characterizes some dynamic processes on
networks such as consensus algorithms for multi-agent networks. In this paper, we prove that the algebraic connectivity of any complete multipartite graph is not less thanthat of all graphs obtained from it by applying a 2-switch.
This is a generalization of the authors’ previous result aboutcomplete bipartite graphs.
1. Introductionof six vertices or more is a local maximizer of the algebraic
connectivity in the sense that it has the largest algebraic
connectivity among all graphs in the neighborhood, where
the neighborhood of a graph G is defined as the set of allgraphs that can be obtained from G by applying a 2-switch.
A 2-switch is a well-known graph transformation that does
not change the degree sequence [6].
In this paper, as a generalization of the authors’ previous
result [5], we prove that any complete multipartite graph isa local maximizer of the algebraic connectivity in the same
sense as above. We first review definitions of the algebraic
connectivity maximizing (ACM) graph and the algebraic
connectivity locally maximizing (ACLM) graph. We next
study some properties of eigenvalues and eigenvectors of
the Laplacian matrix of the complete multipartite graph.
We finally present the main results of this paper.

The algebraic connectivity [1], which is defined as thesecond smallest eigenvalue of the Laplacian matrix, indicates how well the network is connected. The algebraic
connectivity also characterizes some dynamic processes on
multi-agent networks. For example, the convergence rateof the average consensus algorithm proposed by OlfatiSaber and Murray [2] is determined by the algebraic connectivity of the communication graph. Therefore, finding graphs with a high algebraic connectivity under certain
constraints on the topology is an important problem fromboth a theoretical and a practical point of view.
Ogiwara et al. [3, 4] considered the problem of finding
graphs that maximize or locally maximize the algebraic
connectivity in the space of graphs with a fixed numberof vertices and edges. They proved that some well-knownclasses such as star graphs, cycle graphs, complete bipartite
graphs maximize the algebraic connectivity under certain
conditions. They also proved that cycle graphs, complete
bipartite graphs, and circulant graphs locally maximize thealgebraic connectivity.
Recently, the authors of the present paper studied the
problem of finding graphs that maximize or locally maximize the algebraic connectivity in the space of graphs witha fixed degree sequence [5]. This is closely related tothe problem in which a communication topology has to befound for the fastest or nearly fastest consensus when thenumber of communication channels for each agent is fixed.
They proved that any complete bipartite graph composed

Because L(G) is always positive semi-definite, its eigenvalues are real and nonnegative. So we hereafter denotethem by λ1 (G) ≤ λ2 (G) ≤ · · · ≤ λn (G). Furthermore, because L(G)1 = 0 holds, where 1 and 0 are the vectors of
all ones and all zeros, respectively, the smallest eigenvalueof L(G) is always zero, that is, λ1 (G) = 0.
The algebraic connectivity [1] is defined as follows.

This work was supported by JSPS KAKENHI Grant Number
15K00035.

Definition 1 The second smallest eigenvalue λ2 (G) of
L(G) is called the algebraic connectivity of the graph G.

2. Algebraic Connectivity Locally Maximizing Graph
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 Laplacian matrix of G is defined by
L(G) = D(G) − A(G)where A(G) = (ai j (G)) is the adjacency matrix defined by{
1, if {i, j} ∈ E(G),ai j (G) =0, otherwise,
and D(G) is the degree matrix defined by
di (G) = |{ j | {i, j} ∈ E(G)}| .

- 285 -

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 E(G) contains {p, q} and {r, s} but neither{i, k} nor { j, l}. Let G′ = (V(G′ ), E(G′ )) be the graph obtained from G by removing two edges {p, q} and {r, s}, andby adding two new edges {p, r} and {q, s} (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 [6].
We now present definitions of algebraic connectivity
maximizing graphs and algebraic connectivity locally maximizing graphs, both of which were first introduced in [5].

Figure 2: Complete 4-partite graph K1,1,2,4 . The algebraic
connectivity of this graph is 4.
ACM graph in GD(G) . We next consider the case where
all graphs in ND(G) (G) are isomorphic to G. Suppose that
there exists a G′ ∈ GD(G) that is not isomorphic to G. Let
G0 (= G), G1 , . . . , Gk−1 , Gk (= G′ ) be a sequence of graphs
such that Gi+1 is obtained from Gi by a 2-switch. Then
there exists an i (≥ 2) such that Gi is isomorphic to G1 but
Gi+1 is not. However, this contradicts the assumption thatall graphs in ND(G) (G) are isomorphic to G. Therefore, we
conclude that all graphs in GD(G) are isomorphic to G andhence G is an ACM graph in GD(G) .
□Definition 2 A graph G is called an algebraic connectivity
maximizing (ACM) graph in GD(G) if∀G′ ∈ GD(G) ,3. Complete Multipartite Graphs are Algebraic Connectivity Locally Maximizing Graphs

λ2 (G) ≥ λ2 (G′ ) ,where GD(G) is the set of all graphs having the same degree
matrix as G.
Definition 3 A graph G is called an algebraic connectivity
locally maximizing (ACLM) graph in GD(G) if∀G′ ∈ ND(G) (G),λ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 G is an ACM
graph in GD(G) then G is an ACLM graph in GD(G) . However, the converse is not true.
The following lemma shows that in some special cases G
can be proved to be an ACM graph in GD(G) by examining
only graphs in ND(G) (G).
Lemma 1 If ND(G) (G) = ∅ or all graphs in ND(G) (G) are
isomorphic to G then G is an ACM graph in GD(G) .
Proof: We first consider the case where ND(G) (G) = ∅.
Suppose that GD(G) contains a graph G′ that is not G. Then
G can be transformed into G′ by applying 2-switches sequentially, and hence ND(G) (G) must contain at least one
graph. However, this contradicts ND(G) (G) = ∅. Therefore, we conclude that GD(G) = {G} and hence G is the

If the vertex set V(G) of a graph G is partitioned intok (≥ 2) disjoint nonempty subsets V1 , V2 , . . . , Vk such thattwo vertices i and j are adjacent if and only if they belong to diﬀerent subsets, then G is called a complete kpartite graph and denoted by Kn1 ,n2 ,...,nk where nl = |Vl | forl = 1, 2, . . . , k. A complete multipartite graph is shown in
Fig.2. In the following, we assume without loss of generality that n1 ≤ n2 ≤ · · · ≤ nk . Also, we denote the index of
the subset to which vertex i belongs by π(i), that is, i ∈ Vπ(i)∑for i = 1, 2, . . . , n (= kl=1 nl ). Then the Laplacian matrix
L(Kn1 ,n2 ,...,nk ) is given by
n − nπ(i) , if i = j,0,if π(i) = π( j) and i , j,
L(Kn1 ,n2 ,...,nk )i j = 


 −1,
if π(i) , π( j).
It is well known that eigenvalues of the Laplacian matrixof Kn1 ,n2 ,...,nk are 0, n − nk , n − nk−1 , . . . , n − n1 , n and theirmultiplicities are 1, nk − 1, nk−1 − 1, . . . , n1 − 1, k − 1, respectively. In this section, we show that any complete k-partite
graph Kn1 ,n2 ,...,nk is an ACLM graph in GD(Kn1 ,n2 ,...,nk ) .
Lemma 2 Suppose we are given a complete multipartite
graph Kn1 ,n2 ,...,nk . Let v = (v1 , v2 , . . . , vn )T be any vector
such that i) ∥v∥ , 0, ii) vi = 0 for all i < Vk , and iii) v T 1 =0. Then v is an eigenvector of L(Kn1 ,n2 ,...,nk ) associated withλ2 (Kn1 ,n2 ,...,nk ) = n − nk .

- 286 -

Proof: Let v be any vector satisfying the three conditions.
Then, for any i such that i < Vk (or π(i) , k), we havegraph obtained from G3 by adding {q, s}. Then it is obvious that G ∈ ND(Kn1 ,n2 ,...,nk ) . We show in the following thatλ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ). By Interlace theorem [7], we have

(L(Kn1 ,n2 ,...,nk )v)i∑∑
L(Kn1 ,n2 ,...,nk )i j v j = −v j = 0 = (n − nk )vi .
=λ2 (G1 ) ≤ λ2 (Kn1 ,n2 ,...,nk ) ≤ λ3 (G1 )≤ λ3 (Kn1 ,n2 ,...,nk ) ≤ λ4 (G1 ) ≤ λ4 (Kn1 ,n2 ,...,nk ) ,λ3 (G1 ) ≤ λ3 (G2 ) ≤ λ4 (G1 ) ,λ3 (G3 ) ≤ λ3 (G2 ) ≤ λ4 (G3 ) ,

j∈Vk

j∈Vk

Also, for any i such that i ∈ Vk (or π(i) = k), we have∑
(L(Kn1 ,n2 ,...,nk )v)i =L(Kn1 ,n2 ,...,nk )i j v j = (n − nk )vi .

λ2 (G) ≤ λ3 (G3 ) ≤ λ3 (G) ≤ λ4 (G3 ) ≤ λ4 (G) .

j∈Vk

Therefore, v satisfies L(Kn1 ,n2 ,...,nk )v = (n−nk )v which completes the proof.
□

Lemma 3 If nk−1 = 1, ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk ) is the empty
set. If nk−1 = nk = 2, all graphs in ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk )are isomorphic to Kn1 ,n2 ,...,nk .
Proof: Suppose first that nk = 1. Then Kn1 ,n2 ,...,nk is a complete graph, and hence ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk ) = ∅. Suppose next that nk−1 = 1 and nk ≥ 2. In this case, because allpairs of vertices, except pairs of vertices in Vk , are adjacent,there are no four vertices p, q, r, s such that E(Kn1 ,n2 ,...,nk )contains both {p, q} and {r, s} but neither {p, r} nor {q, s}.
Suppose finally that nk−1 = nk = 2. In this case, there
exist four vertices p, q, r, s such that E(Kn1 ,n2 ,...,nk ) contains
both {p, q} and {r, s} but neither {p, r} nor {q, s}. We assume
without loss of generality that Vk−1 = {p, r} and Vk = {q, s}.
Then p, q, r, s are adjacent to all vertices except r, s, p, q,
respectively. Let G be the graph obtained from Kn1 ,n2 ,...,nk
by applying a 2-switch to these four vertices as shown in
Fig.1. Then, in G, vertices p, q, r, s are adjacent to all vertices except q, p, s, r, respectively. If we relabel vertices in
G as q → r and r → q, the resulting graph is identical toKn1 ,n2 ,...,nk . Therefore, G is isomorphic to Kn1 ,n2 ,...,nk .
□From Lemmas 1 and 3, we have the following result.
Corollary 1 If nk−1 = 1 or nk−1 = nk = 2, Kn1 ,n2 ,...,nk is an
ACM graph in GD(Kn1 ,n2 ,...,nk ) .
Now we give the first main theorem of this paper.

From these inequalities, we have λ2 (G) ≤ λ4 (Kn1 ,n2 ,...,nk ).
Also, it follows from the assumption nk ≥ 4 that the multiplicity nk − 1 of λ2 (Kn1 ,n2 ,...,nk ) is at least three, which meansthat λ4 (Kn1 ,n2 ,...,nk ) = λ2 (Kn1 ,n2 ,...,nk ). Therefore, we conclude
that λ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ).
□We next give the second main theorem of this paper,
which takes a diﬀerent approach to show that any Kn1 ,n2 ,...,nkwith nk−1 ≥ 2 and nk ≥ 3 is an ACLM graph.
Theorem 2 Any Kn1 ,n2 ,...,nk is an ACLM graph in
GD(Kn1 ,n2 ,...,nk ) . Furthermore, if nk−1 ≥ 2 and nk ≥ 3, there
exists at least one graph G in ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk ) suchthat
λ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ) − 1 +1
2≤ λ2 (Kn1 ,n2 ,...,nk ) − . (1)nk
3Proof: Because it has already been shown by Corollary 1that Kn1 ,n2 ,...,nk is an ACM graph in GD(Kn1 ,n2 ,...,nk ) if nk−1 = 1
or nk−1 = nk = 2, we assume in the following that nk−1 ≥ 2
and nk ≥ 3. Let p, q, r, s be any four vertices such that
E(Kn1 ,n2 ,...,nk ) contains {p, q} and {r, s} but neither {p, r} nor{q, s} (Existence of such four vertices is guaranteed by theassumption that nk−1 ≥ 2 and nk ≥ 3). Then we easily seethat
π(p) = π(r) , π(q) = π(s) .
(2)
Let G be the graph obtained from Kn1 ,n2 ,...,nk by applying a
2-switch to four vertices p, q, r and s as shown in Fig. 1.
Then the Laplacian matrix of G is given by
L(G) = L(Kn1 ,n2 ,...,nk ) − M
where M = (mi j ) is given by
−1, if (i, j) ∈ {(p, q), (q, p), (r, s), (s, r)} ,1,
if (i, j) ∈ {(p, r), (r, p), (q, s), (s, q)} ,mi j =  0,otherwise .

Theorem 1 Any Kn1 ,n2 ,...,nk with nk ≥ 4 is an ACLM graphin GD(Kn1 ,n2 ,...,nk ) .
Proof: If ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk ) = ∅ then Kn1 ,n2 ,...,nk is an
ACLM graph as explained in the previous section. Thus
we hereafter assume that ND(Kn1 ,n2 ,...,nk ) (Kn1 ,n2 ,...,nk ) , ∅. Letp, q, r, s be any four vertices such that E(Kn1 ,n2 ,...,nk ) contains {p, q} and {r, s} but neither {p, r} nor {q, s}. Let G1 be
the graph obtained from Kn1 ,n2 ,...,nk by removing {p, q}, G2
be the graph obtained from G1 by adding {p, r}, G3 be thegraph obtained from G2 by removing {r, s}, and G be theSince λ2 (G) is expressed as
λ2 (G) =minv T 1=0, ∥v∥=1

v T L(G)v,

we can find an upper bound for λ2 (G) by substituting any
v such that v T 1 = 0 and ∥v∥ = 1 into v T L(G)v. Let us
now assume that v satisfies the condition that vi = 0 for- 287 -

all i < Vk in addition to v T 1 = 0 and ∥v∥ = 1. Then, by
Lemma 2, v is a unit eigenvector of L(Kn1 ,n2 ,...,nk ) associatedwith λ2 (Kn1 ,n2 ,...,nk ). We therefore have
λ2 (G) ≤=v T L(G)v
λ2 (Kn1 ,n2 ,...,nk ) − v T Mv=

λ2 (Kn1 ,n2 ,...,nk )+ 2v p vq + 2vr v s − 2v p vr − 2vq v s .

(3)

We first consider the case where p < Vk (or π(p) , k) andq < Vk (or π(q) , k). In this case, because v p = vq = vr =v s = 0, it follows from (3) that λ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ). We
next consider the case where either p ∈ Vk (or π(p) = k) orq ∈ Vk (or π(q) = k) holds. We assume without loss of generality that the former holds. In this case, because vq = v s =0, it follows from (3) that λ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ) − 2v p vr .
In the following, we focus our attention on the minimum
value of the second term −2v p vr under the constraints onv mentioned above. This minimum value can be found bysolving the mathematical programming problem:
minimize −2v p vr∑
subject tov = 0,∑i∈Vk 2iv
i∈Vk i = 1 .

(4)

Using the method of Lagrange multiplier, we obtain an optimal solution of (4) which is given by{ µ1, if i ∈ {p, r},2)v∗i = 2(1−µ(5)µ1− 2µ2 ,
if i ∈ Vk \ {p, r}
where

√
µ1 =

8(nk − 2)n3k

and µ2 =nk − 2
.
nk

2
.
nk

2
nk

which completes the proof.

□

In order to see how tight the upper bound given in (1)is, we consider a graph that can be obtained from K1,1,2,4
shown in Fig. 2 by applying a 2-switch. Removing edges{3, 5} and {4, 6} and adding new edges {3, 4} and {5, 6}, wehave the graph shown in Fig. 3. The algebraic connectivityof the obtained graph is 3.2679492, while the right-handside of (1) is given by2
λ2 (K1,1,2,4 ) − 1 + = 3.5
4which is slightly greater than the true value.

We have proved that any complete multipartite graph
Kn1 ,n2 ,...,nk is an ACLM graph in the space of graphs with thesame degree sequence. We have also proved that if nk−1 ≥ 2
and nk ≥ 3 then there are four vertices in Kn1 ,n2 ,...,nk such thatthe application of a 2-switch to the four vertices decreases
the algebraic connectivity by at least 1/3. One of the future
problems is to prove that any complete multipartite graphis an ACM graph.
References[1] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Mathematical Journal, vol. 23, no. 98,
pp. 298–305, 1973.

[3] 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, September 2011,
pp. 56–59.

Therefore, we have
λ2 (G) ≤ λ2 (Kn1 ,n2 ,...,nk ) − 1 +4. Conclusion[2] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networks of dynamic agents,” in Proceedingsof the 2003 American Control Conference, June 2003,
pp. 951–956.

Substituting (5) to the objective function of (4), we have
−2v p vr = −1 +Figure 3: The graph obtained from K1,1,2,4 shown in Fig. 2
by removing {3, 5} and {4, 6} and adding {3, 4} and {5, 6}.
The algebraic connectivity of this graph is 3.2679492.

[4] K. Ogiwara, T. Fukami, and N. Takahashi, “Maximizing algebraic connectivity in the space of graphs with
fixed number of vertices and edges,” submitted.
[5] T. Fujihara and N. Takahashi, “On graphs that locallymaximize algebraic connectivity in the space of graphswith the fixed degree sequence,” in Proceedings of2014 International Symposium on Nonlinear Theory
and its Applications, 2014, pp. 353–356.
[6] D. B. West, Introduction to Graph Theory, Second Edition. Prentice Hall, 2001.
[7] C. D. Godsil and G. Royle, Algebraic Graph Theory.
Springer New York, 2001.

- 288 -