# The Least Algebraic Connectivity of Graphs

Authors: Guisheng Jiang; Guidong Yu; Jinde Cao
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

The algebraic connectivity of a graph is defined as the second smallest eigenvalue of the Laplacian matrix of the graph, which is a parameter to measure how well a graph is connected. In this paper, we present two unique graphs whose algebraic connectivity attain the minimum among all graphs whose complements are trees, but not stars, and among all graphs whose complements are unicyclic graphs, but not stars adding one edge, respectively.


---

## Body

## 1. Introduction

LetG
=
(
V
(
G
)
,
E
(
G
)
) be a simple graph with vertex set V
(
G
)
=
{
v
1
,
v
2
,
…
,
v
n
}. Thecomplement of G is denoted by G
c
∶
=
(
V
(
G
)
,
E
′
(
G
)
), where E
′
(
G
)
=
{
x
y
:
x
,
y
∈
V
(
G
)
,
x
y
∉
E
(
G
)
}. Theadjacency matrix of G is defined to be a matrix A
(
G
)
=
[
a
i
j
] of order n, where a
i
j
=
1 if v
i is adjacent to v
j, and a
i
j
=
0 otherwise. The degree matrix of G is denoted by D
(
G
)
=
d
i
a
g
d
G
(
v
1
)
,
d
G
(
v
2
)
,
…
,
d
G
(
v
n
), where d
G
(
v
) denotes the degree of a vertex v in the graph G. The matrix Q
(
G
)
=
D
(
G
)
+
A
(
G
) is thesignless Laplacian matrix of G. TheLaplacian matrix of G is defined to be L
(
G
)
=
D
(
G
)
-
A
(
G
). Since A
(
G
), Q
(
G
), and L
(
G
) are real and symmetric, their eigenvalues are real and can be arranged, respectively. We simply call the eigenvalues of A
(
G
) as eigenvalues of G, the largest eigenvalue of A
(
G
) as spectral radius of G, the eigenvalues of Q
(
G
) asthe signless Laplacian eigenvalues of G, and the eigenvalues of L
(
G
) asthe Laplacian eigenvalues of G. The second smallest Laplacian eigenvalue of G is calledthe algebraic connectivity of  G, denoted by a
(
G
). The eigenvectors corresponding to a
(
G
) are calledFiedler vectors of  G. a
(
G
) is a good parameter to measure how well a graph is connected and plays an important role in control theory and communications, and so forth. In particular, it is related to the synchronization ability of complex network [1, 2]. On the other hand it is related to the convergence speed in networks; one important topic is to increase a
(
G
) as much as possible. There are several techniques to enhance this metric; see [3].When the structures of graphs are very complex, but the structures of their complements are simple, we naturally think whether we can study the graphs by studying their complements. Recently, there are some works about this subject. A connected graphG with n vertices and m edges is called k
-cyclic graph if m
=
n
-
1
+
k. Specially, if k
=
0,1
,
2, or 3, then G is called a tree, unicyclic graph, bicyclic graph, or tricyclic graph, respectively. Let T
n be the set of trees on n vertices, and let S
n be the set of unicyclic graphs of order n. Denote by K
1
,
n
-
1 the star graph on n vertices, and K
1
,
n
-
1
+
e the graph obtained from K
1
,
n
-
1 by adding one edge e. Fan et al. [4] have got the unique minimizing graph whose least eigenvalue attains the minimum among all graphs G for G
c
∈
T
n
∖
{
K
1
,
n
-
1
}. Li and Wang [5] have researched the unique minimizing graph which whose signless Laplacian eigenvalue attains the minimum among all graphs G for G
c
∈
T
n
∖
{
K
1
,
n
-
1
}. Liu and Zhang [6] have studied the unique maximizing graph whose spectral radius attains the maximum among all graphs G for G
c
∈
S
n. Yin and Guo [7, 8] have characterized two maximizing graphs whose spectral radius attains the maximum among all the complements of bicyclic graphs of order n and among all the complements of tricyclic graphs of order n, respectively. Yu and Fan [9, 10] have studied two unique minimizing graphs whose least eigenvalue attains the minimum among all graphs of order n whose complements are connected and whose complements are connected and have no cut edges or cut vertices, that is, 2-edge connected or 2-vertex connected graphs, respectively.We note that the least Laplacian eigenvalue of a graph is zero, and Fiedler [11] proves that a graph G is connected if and only if a
(
G
)
>
0. In fact, K
1
,
n
-
1 is the unique graph whose complement is not connected in T
n, and K
1
,
n
-
1
+
e is the unique graph whose complement is not connected in S
n. One may naturally ask what is the minimizing graph whose second smallest Laplacian eigenvalue (or the algebraic connectivity) attains the minimum among all graphs G for G
c
∈
T
n
∖
{
K
1
,
n
-
1
} or for G
c
∈
S
n
∖
{
K
1
,
n
-
1
+
e
}? In this paper, we study those questions and obtain two unique graphs which have the least algebraic connectivity among all graphs G for G
c
∈
T
n
∖
{
K
1
,
n
-
1
} and for G
c
∈
S
n
∖
{
K
1
,
n
-
1
+
e
}, in Sections 3 and 4, respectively.


## 2. Preliminaries

We begin with some definitions. Given a graphG of order n, a vector X
∈
R
n is called to be defined on G, if there is a 1-1 map φ from V
(
G
) to the entries of X, simply written X
u
=
φ
(
u
) for each u
∈
V
(
G
). If X is an eigenvector of L
(
G
), then X is defined on G naturally; X
u is the entry of X corresponding to the vertex u. One can find that, for an arbitrary vector X
∈
R
n, (1)
X
T
L
G
X
=
∑
u
v
∈
E
G
‍
X
u
-
X
v
2
,and when μ is a Laplacian eigenvalue of G corresponding to the eigenvector X if and only if X
≠
0, (2)
d
G
v
-
μ
X
v
=
∑
u
∈
N
G
v
‍
X
u
,
f
o
r
e
a
c
h
v
e
r
t
e
x
v
∈
V
G
,where N
G
(
v
) denotes the neighborhood of v in the graph G. Equation (2) is called the Laplacian eigenvalue-equation for the graph G. In addition, by the well-known Courant-Fisher Theorem [11], for an arbitrary unit vector X
∈
R
n, when X
≠
0, X
⊥
1,(3)
a
G
≤
X
T
L
G
X
,with equality if and only if X is a Fiedler vector of G, where 0 is null vector and 1 is the vector such that each of its coordinates is equal to 1.LetG
c be the complement of a graph G of order n. It is easily seen that L
(
G
c
)
=
n
I
-
J
-
L
(
G
), where J
,
I
, respectively, denote the all-ones square matrix and the identity matrix both of suitable sizes. So for an arbitrary vector X
∈
R
n, (4)
X
T
L
G
c
X
=
X
T
n
I
-
J
X
-
X
T
L
G
X
.Lemma 1 (see [11]).
LetG be a simple graph. Then a
(
G
)
≤
δ
(
G
), where δ
(
G
)
=
m
i
n
{
d
G
(
v
)
,
v
∈
V
(
G
)
}.Lemma 2.
If{
X
i
,
i
=
1,2
,
…
,
n
} is a nonincreasing sequence, then, for any 1
≤
i, j
≤
n, (
X
i
-
X
j
)
2
≤
m
a
x
{
(
X
i
-
X
1
)
2
,
(
X
i
-
X
n
)
2
}
≤
(
X
1
-
X
n
)
2.Proof.
For any1
≤
i, j
≤
n, if X
i
-
X
j
≥
0, by the monotone of {
X
i
,
i
=
1,2
,
…
,
n
}, we have (5)
0
≤
X
i
-
X
j
≤
X
i
-
X
n
≤
X
1
-
X
n
.
Then(6)
X
i
-
X
j
2
≤
X
i
-
X
n
2
≤
X
1
-
X
n
2
.
Similarly, ifX
i
-
X
j
≤
0, we have(7)
0
≥
X
i
-
X
j
≥
X
i
-
X
1
≥
X
n
-
X
1
.
Then(8)
X
i
-
X
j
2
≤
X
i
-
X
1
2
≤
X
1
-
X
n
2
.
The result follows.


## 3. The least Algebraic Connectivity of the Complements of Trees

Given a graphG with u
,
v
∈
V
(
G
), let d
G
(
u
,
v
) be the distance between u and v in G. Denote by K
p
,
q a complete bipartite graph whose bipartition has p vertices and q vertices, respectively. Denote by T
(
p
,
q
) the special tree, which is obtained from two disjoint stars K
1
,
p (p
≥
1) and K
1
,
q (q
≥
1) by joining the center of K
1
,
p and K
1
,
q by a path of length 1; see Figure 1.Figure 1
The graphT
(
p
,
q
).Lemma 3.
Given a positive integern (n
≥
6), for any positive integers p
,
q with p
+
q
=
n
-
2, p
≥
q
≥
2, one has(9)
a
T
p
,
q
c
>
a
T
p
+
1
,
q
-
1
c
.Proof.
LetT
(
p
,
q
) be the graph as depicted in Figure 1 with some vertices labeled. Let X be a unit Fiedler vector of T
(
p
,
q
)
c. By Lemma 1, we have a
(
T
(
p
,
q
)
c
)
≠
d
T
(
p
,
q
)
c
(
v
)
+
1 for any vertex v
∈
V
(
T
(
p
,
q
)
c
). Then by the Laplacian eigen-equations (2), all vertices which are the pendant vertices of v
2 have the same values given by X, say X
1; all vertices which are the pendant vertices of v
3 have the same values given by X, say X
4. Write X
2
∶
=
X
v
2, X
3
∶
=
X
v
3. Now considering the Laplacian eigen-equations of X for T
(
p
,
q
)
c, and simply writing a
:
=
a
(
T
(
p
,
q
)
c
), we have(10)
p
+
q
-
a
X
1
=
p
-
1
X
1
+
X
3
+
q
X
4
,
q
-
a
X
2
=
q
X
4
p
-
a
X
3
=
p
X
1
p
+
q
-
a
X
4
=
p
X
1
+
X
2
+
q
-
1
X
4
.Transform (10) into a matrix equation B
-
a
I
X
′
=
0, where X
′
=
(
X
1
,
X
2
,
X
3
,
X
4
)
T and (11)
B
=
q
+
1
0
-
1
-
q
0
q
0
-
q
-
p
0
p
0
-
p
-
1
0
p
+
1
.
Letf
(
μ
;
p
,
q
)
∶
=
d
e
t
(
μ
I
-
B
); then we have(12)
f
μ
;
p
,
q
=
μ
4
-
2
p
+
q
+
1
μ
3
+
p
2
+
3
p
q
+
2
p
+
q
2
+
2
q
+
1
μ
2
-
p
q
p
+
q
+
2
μ
.
Because0 and a are roots of the polynomial f
(
μ
;
p
,
q
), then a is the second smallest root of the polynomial f
(
μ
;
p
,
q
). Observe that(13)
f
μ
;
p
+
1
,
q
-
1
-
f
μ
;
p
,
q
=
μ
q
-
p
-
1
μ
-
p
-
q
-
2
=
μ
q
-
p
-
1
μ
-
n
.
By Lemma1, we have a
=
a
(
T
(
p
,
q
)
c
)
<
n. Then by p
≥
q, a
>
0, and f
(
a
;
p
,
q
)
=
0, we have that (14)
f
a
;
p
+
1
,
q
-
1
=
a
q
-
p
-
1
a
-
n
>
0
,which implies that (15)
a
T
p
+
1
,
q
-
1
c
<
a
T
p
,
q
c
.
The result now follows from the above discussion.Corollary 4.
Given a positive integern (n
≥
6), for any positive integers p
,
q with p
+
q
=
n
-
2, p
≥
q
≥
2, one has(16)
a
T
p
,
q
c
>
a
T
p
+
1
,
q
-
1
c
>
⋯
>
a
T
n
-
3,1
c
.Lemma 5.
Given a positive integern (n
≥
4), for any tree T
∈
T
n
∖
{
K
1
,
n
-
1
}, there exist some integers p
,
q with 1
≤
p, q
≤
n
-
3, p
+
q
=
n
-
2, such that (17)
a
T
c
≥
a
T
p
,
q
c
.Proof.
LetX be a unit Fiedler vector of T
c; then X
≠
0 and X
⊥
1. Thus we can get a sequence {
X
v
i
,
i
=
1,2
,
…
,
n
} such that (18)
X
v
1
≥
X
v
2
≥
⋯
≥
X
v
n
.
Ifd
T
(
v
1
,
v
n
)
>
1, we can let the path v
1
T
v
n
=
v
1
u
1
⋯
u
2
v
n, where u
1
=
u
2 when d
T
(
v
1
,
v
n
)
=
2. Add the edge v
1
v
n, and delete the edge v
1
u
1 or u
2
v
n such that the result tree T
∗ is not star. Then, by (1) and Lemma 2, we have(19)
X
T
L
T
X
=
∑
v
i
v
j
∈
E
T
X
v
i
-
X
v
j
2
≤
∑
v
i
v
j
∈
E
T
∗
X
v
i
-
X
v
j
2
=
X
T
L
T
∗
X
.
IfT
∗
≇
T
(
p
,
q
) and there exists a pendant vertex v, whose neighbor u is neither v
1 nor v
n, satisfying(20)
X
v
-
X
v
1
2
≥
X
v
-
X
v
n
2
,then delete u
v and add v
v
1; otherwise delete u
v and add v
v
n. Repeat this rearranging until the resulting tree T
′
≅
T
(
p
,
q
). By (1) and Lemma 2, we have(21)
X
T
L
T
∗
X
=
∑
v
i
v
j
∈
E
T
∗
X
v
i
-
X
v
j
2
≤
∑
v
i
v
j
∈
E
T
′
X
v
i
-
X
v
j
2
=
X
T
L
T
p
,
q
X
.
By (3), (4), (19), and (21), we have(22)
a
T
c
=
X
T
L
T
c
X
=
X
T
n
I
-
J
X
-
X
T
L
T
X
≥
X
T
n
I
-
J
X
-
X
T
L
T
p
,
q
X
=
X
T
L
T
p
,
q
c
X
≥
a
T
p
,
q
c
.The result follows.By Corollary4 and Lemma 5, we now obtain one main result of this paper.Theorem 6.
Forn
≥
4, T
∈
T
n
∖
{
K
1
,
n
-
1
}, one has(23)
a
T
c
≥
a
T
n
-
3,1
c
,with equality if and only if T
≅
T
(
n
-
3,1
).


## 4. The Least Algebraic Connectivity of the Complements of Unicyclic Graphs

Denote byG
1
(
p
,
q
) the special unicyclic graph, which is obtained from C
3 by identifying two vertices with the center of K
1
,
p and the center of K
1
,
q, respectively; see Figure 2.Figure 2
The graphG
1
(
p
,
q
).Lemma 7.
Given a positive integern (n
≥
7), for any positive integers p
,
q with p
+
q
=
n
-
3, p
≥
q
≥
2, we have (24)
a
G
1
p
,
q
c
>
a
G
1
p
+
1
,
q
-
1
c
.Proof.
LetG
1
(
p
,
q
) be the graph as depicted in Figure 2 with some vertices labeled. Let X be a unit Fiedler vector of G
1
(
p
,
q
)
c. By Lemma 1, we have a
(
G
1
(
p
,
q
)
c
)
≠
d
G
1
(
p
,
q
)
c
(
v
)
+
1 for any vertex v
∈
V
(
G
1
(
p
,
q
)
c
). Then, by the Laplacian eigen-equations (2), all vertices which are the pendant vertices of v
2 have the same values given by X, say X
4; all vertices which are the pendant vertices of v
3 have the same values given by X, say X
5. Write X
i
∶
=
X
v
i
i
=
1,2
,
3. Now considering the Laplacian eigen-equations of X for G
1
(
p
,
q
)
c, and simply writing a
∶
=
a
(
G
1
(
p
,
q
)
c
), we have(25)
p
+
q
-
a
X
1
=
p
X
4
+
q
X
5
,
q
-
a
X
2
=
q
X
5
p
-
a
X
3
=
p
X
4
p
+
q
+
1
-
a
X
4
=
X
1
+
X
3
+
p
-
1
X
4
+
q
X
5
p
+
q
+
1
-
a
X
5
=
X
1
+
X
2
+
p
X
4
+
q
-
1
X
5
.Transform (25) into a matrix equation B
-
a
I
X
′
=
0, where X
′
=
(
X
1
,
X
2
,
X
3
,
X
4
,
X
5
)
T and (26)
B
=
p
+
q
0
0
-
p
-
q
0
q
0
0
-
q
0
0
p
-
p
0
-
1
0
-
1
q
+
2
-
q
-
1
-
1
0
-
p
p
+
2
.
Letf
1
(
μ
;
p
,
q
)
∶
=
d
e
t
(
μ
I
-
B
); then we have(27)
f
1
μ
;
p
,
q
=
μ
5
-
3
p
+
3
q
+
4
μ
4
+
3
p
2
+
7
p
q
+
8
p
+
3
q
2
+
8
q
+
4
μ
3
-
p
+
q
+
2
p
2
+
4
p
q
+
2
p
+
q
2
+
2
q
μ
2
+
p
q
p
+
q
+
1
p
+
q
+
3
μ
.
Because0 and a are roots of the polynomial f
1
(
μ
;
p
,
q
), then a is the second smallest root of the polynomial f
1
(
μ
;
p
,
q
). Observe that(28)
f
1
μ
;
p
+
1
,
q
-
1
-
f
1
μ
;
p
,
q
=
-
μ
p
-
q
+
1
μ
-
p
-
q
-
1
μ
-
p
-
q
-
3
.
By Lemma1, we have a
=
a
(
G
1
(
p
,
q
)
c
)
≤
q
<
p
+
q
+
1. Then, by p
≥
q
≥
2, a
>
0, and f
1
(
a
;
p
,
q
)
=
0, we have(29)
f
1
a
;
p
+
1
,
q
-
1
=
-
a
p
-
q
+
1
a
-
p
-
q
-
1
a
-
p
-
q
-
3
<
0
,which implies that(30)
a
G
1
p
+
1
,
q
-
1
c
<
a
G
1
p
,
q
c
.
The result now follows from the above discussion.Corollary 8.
Given a positive integern (n
≥
7), for any positive integers p
,
q with p
+
q
=
n
-
3, p
≥
q
≥
2, one has(31)
a
G
1
p
,
q
c
>
a
G
1
p
+
1
,
q
-
1
c
>
⋯
>
a
G
1
n
-
4,1
c
.Denote byG
2
(
p
,
q
) the special unicyclic graph, which is obtained from C
3 by identifying one vertex with the center of K
1
,
p and the pendent vertex of K
1
,
q
+
1; see Figure 3.Figure 3
The graphG
2
(
p
,
q
).Lemma 9.
Given a positive integern (n
≥
8), for any positive integers p
,
q with p
+
q
=
n
-
4, one has(32)
a
G
2
p
,
q
c
>
a
G
2
p
+
1
,
q
-
1
c
,
i
f
p
+
3
>
q
≥
2
a
G
2
p
,
q
c
=
a
G
2
p
+
1
,
q
-
1
c
,
i
f
p
+
3
=
q
a
G
2
p
,
q
c
<
a
G
2
p
+
1
,
q
-
1
c
,
i
f
p
+
3
<
q
.Proof.
LetG
2
(
p
,
q
) be the graph as depicted in Figure 3 with some vertices labeled. Let X be a unit Fiedler vector of G
2
(
p
,
q
)
c. By Lemma 1, we have a
(
G
2
(
p
,
q
)
c
)
≠
d
G
2
(
p
,
q
)
c
(
v
)
+
1 for any vertex v
∈
V
(
G
2
(
p
,
q
)
c
) and a
(
G
2
(
p
,
q
)
c
)
≠
d
G
2
(
p
,
q
)
c
(
v
1
). Write X
i
∶
=
X
v
i, i
=
1,2
,
3,4
,
5,6. Then by the Laplacian eigen-equations (2), X
1
=
X
6, all vertices which are the pendant vertices of v
2 have the same values given by X, namely, X
4; all vertices which are the pendant vertices of v
3 have the same values given by X, namely, X
5. Now considering the Laplacian eigen-equations of X for G
2
(
p
,
q
)
c, and simply writing a
∶
=
a
(
G
2
(
p
,
q
)
c
), we have(33)
p
+
q
+
1
-
a
X
1
=
X
3
+
p
X
4
+
q
X
5
,
q
-
a
X
2
=
q
X
5
,
p
+
2
-
a
X
3
=
2
X
1
+
p
X
4
,
p
+
q
+
2
-
a
X
4
=
2
X
1
+
X
3
+
p
-
1
X
4
+
q
X
5
,
p
+
q
+
2
-
a
X
5
=
2
X
1
+
X
2
+
p
X
4
+
q
-
1
X
5
.Transform (33) into a matrix equation B
-
a
I
X
′
=
0, where X
′
=
(
X
1
,
X
2
,
X
3
,
X
4
,
X
5
)
T and (34)
B
=
p
+
q
+
1
0
-
1
-
p
-
q
0
q
0
0
-
q
-
2
0
p
+
2
-
p
0
-
2
0
-
1
q
+
3
-
q
-
2
-
1
0
-
p
p
+
3
.
Letf
2
(
μ
;
p
,
q
)
∶
=
d
e
t
(
μ
I
-
B
); then we have(35)
f
2
μ
;
p
,
q
=
μ
5
-
3
p
+
3
q
+
9
μ
4
+
3
p
2
+
7
p
q
+
18
p
+
3
q
2
+
20
q
+
27
μ
3
-
p
3
+
5
p
2
q
+
9
p
2
+
5
p
q
2
+
29
p
q
+
27
p
+
q
3
+
13
q
2
+
41
q
+
27
μ
2
+
q
p
+
2
p
+
q
+
3
p
+
q
+
4
μ
.
Because0 and a are roots of the polynomial f
2
(
μ
;
p
,
q
), then a is the second smallest root of the polynomial f
2
(
μ
;
p
,
q
). Observe that(36)
f
2
μ
;
p
+
1
,
q
-
1
-
f
2
μ
;
p
,
q
=
-
μ
p
-
q
+
3
p
+
q
-
μ
+
3
p
+
q
-
μ
+
4
.
Becausef
2
(
a
;
p
,
q
)
=
0, we have(37)
f
2
a
;
p
+
1
,
q
-
1
=
-
a
p
-
q
+
3
p
+
q
-
a
+
3
p
+
q
-
a
+
4
.
By Lemma1, we note that 0
<
a
=
a
(
G
2
(
p
,
q
)
c
)
≤
p
+
q
+
2.
Ifp
+
3
>
q
≥
2, we have f
2
(
a
;
p
+
1
,
q
-
1
)
<
0, which implies that (38)
a
G
2
p
+
1
,
q
-
1
c
<
a
G
2
p
,
q
c
.
Ifp
+
3
=
q, we have f
2
(
a
;
p
+
1
,
q
-
1
)
=
0, which implies that(39)
a
G
2
p
+
1
,
q
-
1
c
=
a
G
2
p
,
q
c
.
Ifp
+
3
<
q, we have(40)
f
2
a
;
p
+
1
,
q
-
1
>
0
,and 0
<
a
=
a
(
G
2
(
p
,
q
)
c
)
≤
p
+
2 by Lemma 1.
Let(41)
f
2
μ
;
p
,
q
=
μ
p
+
q
-
μ
+
3
g
μ
.
Then(42)
g
μ
=
-
μ
3
+
2
p
+
2
q
+
6
μ
2
-
p
2
+
3
p
q
+
6
p
+
q
2
+
8
q
+
9
μ
+
p
2
q
+
p
q
2
+
6
p
q
+
2
q
2
+
8
q
,and a is the least root of the polynomial g
(
μ
) by 0
<
a
≤
p
+
2. We calculate that(43)
g
′
μ
=
-
3
μ
2
+
4
p
+
4
q
+
12
μ
-
p
2
-
3
p
q
-
6
p
-
q
2
-
8
q
-
9
,
g
′
′
μ
=
-
6
μ
+
4
p
+
4
q
+
12
.
Thus when0
<
μ
≤
p
+
2, p
+
3
<
q, g
′
′
(
μ
)
≥
g
′
′
(
p
+
2
)
=
4
q
-
2
p
>
0, which implies that g
′
(
μ
) is monotonously increasing for μ when 0
<
μ
≤
p
+
2
,
p
+
3
<
q.
So, when0
<
μ
≤
p
+
2,  p
+
3
<
q, g
′
(
μ
)
≤
g
′
(
p
+
2
)
=
-
q
2
+
p
q
+
2
p
+
3
<
-
q
-
3
<
0, which implies that g
(
μ
) is monotonously decreasing for μ when 0
<
μ
≤
p
+
2,  p
+
3
<
q.
Then, ifp
+
3
<
q, by f
2
(
a
;
p
+
1
,
q
-
1
)
>
0, we get(44)
a
G
2
p
+
1
,
q
-
1
c
>
a
G
2
p
,
q
c
.
The result now follows from the above discussion.Lemma 10.
Given a positive integern
(
n
≥
8
), for any positive integers p
,
q with p
+
q
=
n
-
4, q
≥
1, one has(45)
a
G
2
p
,
q
c
≥
a
G
2
n
-
5,1
c
,with equality if and only if G
2
(
p
,
q
)
=
G
2
(
n
-
5,1
).Proof.
From the proof of Lemma9, we note that a
1
′
∶
=
a
(
G
2
(
n
-
5,1
)
c
), a
2
′
∶
=
a
(
G
2
(
0
,
n
-
4
)
c
) are the second smallest roots of the following two polynomials, respectively:(46)
f
2
n
-
5,1
=
μ
μ
-
n
+
1
μ
3
+
2
-
2
n
μ
2
=
μ
μ
-
n
w
i
+
n
2
-
n
-
2
μ
+
3
n
-
n
2
,
f
2
0
,
n
-
4
=
μ
μ
-
n
+
1
μ
3
+
2
-
2
n
μ
2
=
μ
μ
-
n
+
1
e
e
+
n
2
-
7
μ
+
8
n
-
2
n
2
.
By Lemma1 and n
≥
8, we have 0
<
a
1
′,  a
2
′
≤
2
<
n
-
1. Thus, a
1
′,  a
2
′ are the least roots of the following two polynomials, respectively:(47)
h
μ
=
μ
3
+
2
-
2
n
μ
2
+
n
2
-
n
-
2
μ
+
3
n
-
n
2
,
k
μ
=
μ
3
+
2
-
2
n
μ
2
+
n
2
-
7
μ
+
8
n
-
2
n
2
.
We observe that(48)
h
μ
-
k
μ
=
n
-
μ
n
-
5
>
0
,for 0
<
μ
≤
2 and n
≥
8.
Becausek
(
a
2
′
)
=
0, n
≥
8, and 0
<
a
2
′
≤
2, we have(49)
h
a
2
′
>
0
,which imply that a
1
′
<
a
2
′; namely, (50)
a
G
2
n
-
5,1
c
<
a
G
2
0
,
n
-
4
c
.
By Lemma9, the result follows.Denote byG
3
(
p
,
q
) the special unicyclic graph, which is obtained from C
4 by identifying two adjacent vertices with the center of K
1
,
p and the center of K
1
,
q, respectively; see Figure 4.Figure 4
The graphG
3
(
p
,
q
).Lemma 11.
Given a positive integern (n
≥
6), for any positive integers p
,
q with p
+
q
=
n
-
4, p
≥
q
≥
1, one has(51)
a
G
3
p
,
q
c
>
a
G
3
p
+
1
,
q
-
1
c
.Proof.
LetG
3
(
p
,
q
) be the graph as depicted in Figure 4 with some vertices labeled. Let X be a unit Fiedler vector of G
3
(
p
,
q
)
c. By Lemma 1, we have a
(
G
3
(
p
,
q
)
c
)
≠
d
G
3
(
p
,
q
)
c
(
v
)
+
1 for any vertex v
∈
V
(
G
3
(
p
,
q
)
c
). Write X
i
∶
=
X
v
i, i
=
1,2
,
3,4
,
5,6. Then by the Laplacian eigen-equations (2), all vertices which are the pendant vertices of v
3 have the same values given by X, namely, X
5; all vertices which are the pendant vertices of v
4 have the same values given by X, namely, X
6. Now considering the Laplacian eigen-equations of X for G
3
(
p
,
q
)
c, and simply writing a
:
=
a
(
G
3
(
p
,
q
)
c
), we have(52)
p
+
q
+
1
-
a
X
1
=
X
3
+
q
X
5
+
p
X
6
,
p
+
q
+
1
-
a
X
2
=
X
4
+
q
X
5
+
p
X
6
,
p
+
1
-
a
X
3
=
X
1
+
p
X
6
,
q
+
1
-
a
X
4
=
X
2
+
q
X
5
,
p
+
q
+
2
-
a
X
5
=
X
1
+
X
2
+
X
4
+
q
-
1
X
5
+
p
X
6
,
p
+
q
+
2
-
a
X
6
=
X
1
+
X
2
+
X
3
+
q
X
5
+
p
-
1
X
6
.
Transform (52) into a matrix equation B
-
a
I
X
′
=
0, where X
′
=
(
X
1
,
X
2
,
X
3
,
X
4
,
X
5
,
X
6
)
T and(53)
B
=
p
+
q
+
1
0
-
1
0
-
q
-
p
0
p
+
q
+
1
0
-
1
-
q
-
p
-
1
0
p
+
1
0
0
-
p
0
-
1
0
q
+
1
-
q
0
-
1
-
1
0
-
1
p
+
3
-
p
-
1
-
1
-
1
0
-
q
q
+
3
.Let f
3
(
μ
;
p
,
q
)
∶
=
d
e
t
(
μ
I
-
B
); then we have(54)
f
3
μ
;
p
,
q
=
μ
6
-
4
p
+
4
q
+
10
μ
5
+
6
p
2
+
13
p
q
+
31
p
+
6
q
2
+
31
q
+
37
μ
4
-
4
p
3
+
15
p
2
q
+
33
p
2
+
15
p
q
2
+
74
p
q
w
w
+
83
p
+
4
q
3
+
33
q
2
+
83
q
+
60
μ
3
+
p
4
+
7
p
3
q
+
13
p
3
+
12
p
2
q
2
+
55
p
2
q
w
e
e
+
55
p
2
+
7
p
q
3
+
55
p
q
2
+
129
p
q
+
86
p
+
q
4
w
e
e
+
13
q
3
+
55
q
2
+
86
q
+
36
μ
2
-
p
+
q
+
3
p
+
q
+
4
·
p
2
q
+
p
2
+
p
q
2
+
3
p
q
+
2
p
+
q
2
+
2
q
μ
.
Because0 and a are roots of the polynomial f
3
(
μ
;
p
,
q
), then a is the second smallest root of the polynomial f
3
(
μ
;
p
,
q
). Observe that(55)
f
3
μ
;
p
+
1
,
q
-
1
-
f
3
μ
;
p
,
q
=
-
μ
p
-
q
+
1
μ
-
p
-
q
-
1
μ
-
p
-
q
-
4
·
μ
-
p
-
q
-
3
.
By Lemma1, we have a
=
a
(
G
3
(
p
,
q
)
c
)
≤
q
+
1. Then by p
≥
q
≥
1, a
>
0, and f
3
(
a
;
p
,
q
)
=
0, we have(56)
f
3
a
;
p
+
1
,
q
-
1
=
-
a
p
-
q
+
1
a
-
p
-
q
-
1
a
-
p
-
q
-
4
·
a
-
p
-
q
-
3
>
0
,which implies that (57)
a
G
3
p
+
1
,
q
-
1
c
<
a
G
3
p
,
q
c
.
The result now follows from the above discussion.Corollary 12.
Given a positive integern (n
≥
6), for any positive integers p
,
q with p
+
q
=
n
-
4, p
≥
q
≥
1, one has(58)
a
G
3
p
,
q
c
>
a
G
3
p
+
1
,
q
-
1
c
>
⋯
>
a
G
3
n
-
4,0
c
.Lemma 13.
Given a positive integern (n
≥
6), for any unicyclic graph G
∈
S
n
∖
{
K
1
,
n
-
1
+
e
}, there exist some integers p
,
q with p
,
q
≥
1, such that (59)
a
G
c
≥
a
G
i
p
,
q
c
,
i
=
1
o
r
2
o
r
3
.Proof.
LetG be obtained from l-cycle C
l (the cycle which has length l) by attaching some trees to it, and let X be a unit Fiedler vector of G
c. Then X
≠
0 and X
⊥
1. Thus we can get a sequence {
X
v
n
} such that(60)
X
v
1
≥
X
v
2
≥
⋯
≥
X
v
n
.
Ifd
G
(
v
1
,
v
n
)
>
1, we can let the path v
1
G
v
n
=
v
1
u
1
⋯
u
2
v
n, where u
1
=
u
2 when d
G
(
v
1
,
v
n
)
=
2. Add the edge v
1
v
n, and delete the edge v
1
u
1 or u
2
v
n such that the result unicyclic graph G
∗ is not K
1
,
n
-
1
+
e. Then, by (1) and Lemma 2, we have(61)
X
T
L
G
X
=
∑
v
i
v
j
∈
E
G
X
v
i
-
X
v
j
2
≤
∑
v
i
v
j
∈
E
G
∗
X
v
i
-
X
v
j
2
=
X
T
L
G
∗
X
,where G
∗ is obtained from C
l
′ by attaching some trees to it and d
G
∗
(
v
1
,
v
n
)
=
1.
IfG
∗
∉
{
G
1
(
p
,
q
)
,
G
2
(
p
,
q
)
,
G
3
(
p
,
q
)
}, we will discuss G
∗ in three cases in the following.
Case  1. Both v
1 and v
n are on the cycle C
l
′.
Ifl
′
≥
5, we can let the cycle C
l
′
=
v
1
v
n
u
1
u
2
u
3
⋯
v
1. In this time, if (
X
u
2
-
X
v
1
)
2
≥
(
X
u
2
-
X
v
n
)
2, we delete the edge u
2
u
3 and add the edge v
1
u
2; otherwise, we delete the edge u
2
u
3 and add the edge u
2
v
n. Then the result unicyclic graph G
∗
∗ is obtained from C
3 (v
n is on the cycle) or C
4 (both v
1 and v
n are on the cycle) by attaching some trees to it.
Case  2. One of v
1
,
v
n is on the cycle C
l
′.
We may letv
1 be on the cycle C
l
′, and it has same discussion when v
n is on the cycle C
l
′. If l
′
≥
4, we can let the cycle C
l
′
=
v
1
u
1
u
2
u
3
⋯
v
1. In this time, if (
X
v
1
-
X
u
2
)
2
≥
(
X
u
2
-
X
v
n
)
2, we delete the edge u
2
u
3 and add the edge v
1
u
2; otherwise, we delete the edge u
2
u
3 and add the edge u
2
v
n. Then the result unicyclic graph G
∗
∗ is obtained from C
3 (one of v
1
,
v
n is on the cycle) or C
4 (both v
1 and v
n are on the cycle) by attaching some trees to it.
Case  3. Neither v
1 nor v
n is on the cycle C
l
′.
We can let the cycleC
l
′
=
u
1
u
2
u
3
⋯
u
1, and neither v
1 nor v
n is on the tree which is attached to u
2. In this time, if (
X
v
1
-
X
u
2
)
2
≥
(
X
u
2
-
X
v
n
)
2, we delete the edge u
2
u
3 and add the edge v
1
u
2; otherwise, we delete the edge u
2
u
3 and add the edge u
2
v
n. Then the result unicyclic graph G
∗
∗ is in Case 1 or Case 2.
Then, by (1) and Lemma 2, we have(62)
X
T
L
G
∗
X
=
∑
v
i
v
j
∈
E
G
∗
X
v
i
-
X
v
j
2
≤
∑
v
i
v
j
∈
E
G
∗
∗
X
v
i
-
X
v
j
2
=
X
T
L
G
∗
∗
X
,where d
G
∗
∗
(
v
1
,
v
n
)
=
1 and G
∗
∗ is obtained from C
3 by attaching some trees to it, where at least one of v
1
,
v
n is on the cycle, or G
∗
∗ is obtained from C
4 by attaching some trees to it, where both v
1 and v
n are on the cycle.
IfG
∗
∗
∉
{
G
1
(
p
,
q
)
,
G
2
(
p
,
q
)
,
G
3
(
p
,
q
)
} and there exists a pendant vertex v, whose neighbor u is neither v
1 nor v
n, satisfying (63)
X
v
-
X
v
1
2
≥
X
v
-
X
v
n
2
,then delete u
v and add v
v
1; otherwise delete u
v and add v
v
n. Repeat this rearranging until the result graph G
∗
∗
∗
∈
{
G
1
(
p
,
q
)
,
G
2
(
p
,
q
)
,
G
3
(
p
,
q
)
}.
Then by (1) and Lemma 2, we have(64)
X
T
L
G
∗
∗
X
=
∑
v
i
v
j
∈
E
G
∗
∗
X
v
i
-
X
v
j
2
≤
∑
v
i
v
j
∈
E
G
∗
∗
∗
X
v
i
-
X
v
j
2
=
X
T
L
G
∗
∗
∗
X
.
According to (3), (4), (61), (62), and (64), we have(65)
a
G
c
=
X
T
L
G
c
X
=
X
T
n
I
-
J
X
-
X
T
L
G
X
≥
X
T
n
I
-
J
X
-
X
T
L
G
∗
X
≥
X
T
n
I
-
J
X
-
X
T
L
G
∗
∗
X
≥
X
T
n
I
-
J
X
-
X
T
L
G
∗
∗
∗
X
=
X
T
L
G
∗
∗
∗
c
X
≥
a
G
∗
∗
∗
c
.The result follows.Theorem 14.
Forn
≥
8, G
∈
S
n
∖
{
K
1
,
n
-
1
+
e
}, one has(66)
a
G
c
≥
a
G
3
n
-
4,0
c
,with equality if and only if G
≅
G
3
(
n
-
4,0
).Proof.
From the proofs of Lemmas7, 9, and 11, we note that a
1
∶
=
a
(
G
1
(
n
-
4,1
)
c
), a
2
∶
=
a
(
G
2
(
n
-
5,1
)
c
), and a
3
∶
=
a
(
G
3
(
n
-
4,0
)
c
) are the second smallest roots of the following three polynomials, respectively:(67)
f
1
μ
;
n
-
4,1
=
μ
5
+
5
-
3
n
μ
4
+
3
n
2
-
9
n
+
3
μ
3
+
-
n
3
+
3
n
2
+
3
n
-
5
μ
2
+
n
3
-
6
n
2
+
8
n
μ
=
μ
μ
4
-
3
n
-
5
μ
3
+
3
n
2
-
9
n
+
3
μ
2
w
=
-
n
3
-
3
n
2
-
3
n
+
5
μ
+
n
3
-
6
n
2
+
8
n
,
f
2
μ
;
n
-
5,1
=
μ
5
+
3
-
3
n
μ
4
+
3
n
2
-
5
n
μ
3
+
-
n
3
+
n
2
+
4
n
-
2
μ
2
+
n
n
-
1
n
-
3
μ
=
μ
μ
-
n
+
1
·
μ
3
+
2
-
2
n
μ
2
+
n
2
-
n
-
2
μ
+
3
n
-
n
2
,
f
3
μ
;
n
-
4,0
=
μ
6
+
6
-
4
n
μ
5
+
6
n
2
-
17
n
+
9
μ
4
+
-
4
n
3
+
15
n
2
-
11
n
μ
3
+
n
4
-
3
n
3
-
5
n
2
+
14
n
-
4
μ
2
+
-
n
4
+
7
n
3
-
14
n
2
+
8
n
μ
=
μ
μ
-
n
+
1
μ
-
n
+
2
·
μ
3
+
3
-
2
n
μ
2
+
n
2
-
2
n
-
2
μ
+
4
n
-
n
2
.
By Lemma1 and n
≥
8, we have 0
<
a
1
,
a
2
,
a
3
≤
1
<
n
-
2. Thus, a
1
,
a
2
,
a
3 are the least roots of the following three polynomials, respectively:(68)
g
1
μ
=
μ
4
-
3
n
-
5
μ
3
+
3
n
2
-
9
n
+
3
μ
2
-
n
3
-
3
n
2
-
3
n
+
5
μ
+
n
3
-
6
n
2
+
8
n
,
g
2
μ
=
μ
3
+
2
-
2
n
μ
2
+
n
2
-
n
-
2
μ
+
3
n
-
n
2
,
g
3
μ
=
μ
3
+
3
-
2
n
μ
2
+
n
2
-
2
n
-
2
μ
+
4
n
-
n
2
.
Claim  1. Consider a
(
G
3
(
n
-
4,0
)
c
)
<
a
(
G
1
(
n
-
4,1
)
c
).
We observe that(69)
f
1
μ
;
n
-
4,1
-
μ
μ
-
n
+
2
g
3
μ
=
μ
2
n
-
μ
-
1
>
0
,for 0
<
μ
≤
1 and n
≥
8.
Becausef
1
(
a
1
;
n
-
4,1
)
=
0, n
≥
8, and 0
<
a
1
≤
1, we have (70)
g
3
a
1
>
0
,which imply that a
3
<
a
1; namely,(71)
a
G
3
n
-
4,0
c
<
a
G
1
n
-
4,1
c
.
Claim  2. a
(
G
3
(
n
-
4,0
)
c
)
<
a
(
G
2
(
n
-
5,1
)
c
).
We observe that(72)
g
2
μ
-
g
3
μ
=
-
μ
2
+
n
μ
-
n
<
0
,for 0
<
μ
≤
1
.
Because0
<
a
3
≤
1 and g
3
(
a
3
)
=
0, we have g
2
(
a
3
)
<
0.
We note that(73)
g
2
′
μ
=
3
μ
2
+
2
2
-
2
n
μ
+
n
2
-
n
-
2
>
2
2
-
2
n
+
n
2
-
n
-
2
=
n
2
-
5
n
+
2
>
0for n
≥
8 and 0
<
μ
≤
1.
Theng
2
(
μ
) is monotonously increasing for u when n
≥
8 and 0
<
μ
≤
1.
Thus byg
2
(
a
3
)
<
0, g
2
(
a
2
)
=
0, and 0
<
a
2,  a
3
≤
1, we gain a
3
<
a
2; that is, (74)
a
G
3
n
-
4,0
c
<
a
G
2
n
-
5,1
c
.
According to Corollary8, Lemma 10, Corollary 12, Lemma 13, Claim 1, and Claim 2, the result follows.



---

*Source: 756960-2015-10-04.xml*