# Bounds of the Spectral Radius and  the Nordhaus-Gaddum Type of the Graphs

Authors: Tianfei Wang; Liping Jia; Feng Sun
Journal: The Scientific World Journal
 (2013)

---

## Abstract

The Laplacian spectra are the eigenvalues of Laplacian matrixL(G)=D(G)-A(G), where D(G) and A(G) are the diagonal matrix of vertex degrees and the adjacency matrix of a graph G, respectively, and the spectral radius of a graph G is the largest eigenvalue of A(G). The spectra of the graph and corresponding eigenvalues are closely linked to the molecular stability and related chemical properties. In quantum chemistry, spectral radius of a graph is the maximum energy level of molecules. Therefore, good upper bounds for the spectral radius are conducive to evaluate the energy of molecules. In this paper, we first give several sharp upper bounds on the adjacency spectral radius in terms of some invariants of graphs, such as the vertex degree, the average 2-degree, and the number of the triangles. Then, we give some numerical examples which indicate that the results are better than the mentioned upper bounds in some sense. Finally, an upper bound of the Nordhaus-Gaddum type is obtained for the sum of Laplacian spectral radius of a connected graph and its complement. Moreover, some examples are applied to illustrate that our result is valuable.


---

## Body

## 1. Introduction

The graphs in this paper are simple and undirected. LetG be a simple graph with n vertices and m edges. For v∈V, denote by dv, mv, and Nv the degree of v, the average 2-degree of v, and the set of neighbors of v, respectively. Then dvmv is the 2-degree of v. Let Δ,  Δ′, δ, and δ′ denote the maximum degree, second largest degree, minimum degree, and second smallest degree of vertices of G, respectively. Obviously, we have Δ′<Δ and δ′>δ. A graph is d-regular if Δ=δ=d.The complement graphGc of G is the graph with the same set of vertices as G, where two distinct vertices are adjacent if and only if they are independent in G. The line graph LG of G is defined by V(LG)=E(G), where any two vertices in LG are adjacent if and only if they are adjacent as edges of G.LetX be a nonnegative square matrix. The spectral radius ρ(X) of X is the maximum eigenvalue of X. Denote by B the adjacency matrix of LG, then ρ(B) is the spectral radius of B. Let D(G) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Then the matrix L(G)=D(G)-A(G) is called the Laplacian matrix of a graph G. Obviously, it is symmetric and positive semidefinite. Similarly, the quasi-Laplacian matrix is defined as Q(G)=D(G)+A(G), which is a nonnegative irreducible matrix. The largest eigenvalue of the Laplacian matrix, denoted by μ(G), is called the Laplacian spectral radius. The Laplacian eigenvalues of a graph are important in graph theory, because they have close relations to many graph invariants, including connectivity, isoperimetric number, diameter, and maximum cut. Particularly, good upper bounds for μ(G) are applied in many fields. For instance, it is used in theoretical chemistry, within the Heilbronner model, to determine the first ionization potential of alkanes, in combinatorial optimization to provide an upper bound on the size of the maximum cut in graph, in communication networks to provide a lower bound on the edge-forwarding index, and so forth. To learn more information on the applications of Laplacian spectral radius and other Laplacian eigenvalues of a graph, see references [1–4].In the recent thirty years, the researchers obtained many good upper bounds forμ(G) [5–8]. These upper bounds improved the previous results constantly. In this paper, we focus on the bounds for the spectral radius of a graph, and the bound of Nordhaus-Gaddum type is also considered, which is the sum of Laplacian spectral radius of a connected graph G and its complement Gc.At the end of this section, we introduce some lemmas which will be used later on.Lemma 1 (see [9]).
LetM=(mij)n×n be an irreducible nonnegative matrix with spectral radius ρ(M), and let Ri(M) be the ith row sum of M; that is,  Ri(M)=∑jmij. Then
(1)min1≤i≤nRi(M)≤ρ(M)≤max1≤i≤nRi(M).
Moreover, if the row sums ofM  are not all equal, then both inequalities are strict.Lemma 2 (see [10]).
LetG=[V,E] be a connected graph with n vertices; then
(2)ρ(G)≤12ρ(LG)+1.
The equality holds if and only ifG is a regular graph.This lemma gives a relation between the spectral radius of a graph and its line graph. Therefore, we can estimate the spectral radius of the adjacency matrix of graph by estimating that of its line graph.Lemma 3 (see [11]).
LetB be a real symmetric n×n matrix, and let ρ(B) be the largest eigenvalue of B. If P(λ) is a polynomial on λ, then
(3)minv∈VRv(P(B))≤P(ρ(B))≤maxv∈VRv(P(B)).
HereRv(P(B)) is the vth row sum of matrix P(B). Moreover, if the row sums of P(B) are not all equal, then both inequalities are strict.Lemma 4 (see [11]).
LetG be a simple connected graph with n vertices and let ρ(Q) be the largest eigenvalue of the quasi-Laplacian matrix of graph G. Then
(4)μ(G)≤ρ(Q),
with equality holds if and only if G is a bipartite graph.By these lemmas, we will give some improved upper bounds for the spectral radius and determine the corresponding extremal graphs.This paper is organized as follows. In Section2, we will give several sharp upper and lower bounds for the spectral radius of graphs and determine the extremal graphs which achieve these bounds. In Section 3, some bounds of Nordhaus-Gaddum type will be given. Furthermore, in Sections 2 and 3, we present some examples to illustrate that our results are better than all of the mentioned upper bounds in this paper, in some sense.


## 2. Bounds on the Spectral Radius

### 2.1. Previous Results

The eigenvalues of adjacency matrix of the graph have wide applications in many fields. For instance, it can be used to present the energy level of specific electrons. Specially, the spectral radius of a graph is the maximum energy level of molecules. Hence, good upper bound for the spectral radius helps to estimate the energy level of molecules [12–15]. Recently, there are some classic upper bounds for the spectral radius of graphs.In the early time Cao [16] gave a bound as follows:
(5)ρ(G)≤2m-δ(n-1)+Δ(δ-1).The equality holds if and only ifG is regular graph or a star plus of K2, or a complete graph plus a regular graph with smaller degree of vertices.Hu [17] obtained an upper bound with simple form as follows:
(6)ρ(G)≤2m-n-δ+2.The equality holds if and only ifG is n-2 regular graph.In 2005, Xu [18] proved that
(7)ρ(G)≤2m-n+1-(δ-1)(n-1-Δ).The equality holds if and only ifG is regular graph or a star graph.Using the average 2-degree of the vertices, the rese-archers got more upper bounds.Cao’s [16] another upper bound:
(8)ρ(G)≤maxu∈V(G)dumu.The equality holds if and only ifG is a regular graph or a semiregular bipartite graph.Similarly, Abrham and Zhang [19] proved that
(9)ρ(G)≤maxuv∈E(G)dudv.The equality holds if and only ifG  is a regular graph or a semiregular bipartite graph.In recent years, Feng et al. [10] give some upper bounds for the spectral radius as follows:
(10)ρ(G)≤maxu∈V(G)du2+dumu2.The equality holds if and only ifG is regular graph. 								(11)ρ(G)≤maxuv∈E(G)du(du+mu)+dv(dv+mv)2.The equality holds if and only ifG is regular graph. 								(12)ρ(G)≤maxu∈V(G)du+dumu2.The equality holds if and only ifG is regular graph. 								(13)ρ(G)≤maxuv∈E(G)du+dv+(du-dv)2+4mumv4.The equality holds if and only ifG is regular graph.


### 2.2. Main Results

All of these upper bounds mentioned in Section2.1 are characterized by the degree and the average 2-degree of the vertices. Actually, we can also use other invariants of the graph to estimate the spectral radius. In the following, such an invariant will be introduced.In a graph, a circle with length 3 is called a triangle. Ifu is a triangle’s vertex in a graph, then u is incident with this triangle. Denote by Tu the number of the triangles associated with the vertex u. For example, in Figure 1, we have Tu = 3 and Tv = Tw= 0.Figure 1
Graph with triangles.LetNu∩Nv be the set of the common adjacent points of vertex u and v; then |Nu∩Nv| present the cardinality of Nu∩Nv.Now, some new and sharp upper and lower bounds for the spectral radius will be given.Theorem 5.
LetG be a simple connected graph with n vertices. Then
(14)ρ(G)≤maxuv∈E(G)du2mu+dv2mv-2(Tu+Tv)2(dudv-|Nu∩Nv|);
the equality holds if and only if G is a regular graph.Proof.
LetK=diag(dudv-|Nu∩Nv|:uv∈E(G)) is a diagonal matrix and B is the adjacency matrix of the line graph. Denote N=K-1BK, then N and B have the same eigenvalues. Since G is a simple connected graph, it is easy to obtain that N is nonnegative and irreducible matrix. The (uv,pq)th entry of N is equal to
(15){dpdq-|Np∩Nq|dudv-|Nu∩Nv|,pq~uv,0,else,
here pq~uv implies that pq and uv are adjacent in graph. Hence, the uvth row sum Ruv(N) of N is
(16)∑pq~uvdpdq-|Np∩Nq|dudv-|Nu∩Nv|=∑q~ududq+∑p~vdpdv-2dudvdudv-|Nu∩Nv|-∑q~u|Nu∩Nq|+∑p~v|Np∩Nv|-2|Nu∩Nv|dudv-|Nu∩Nv|=du2mu+dv2mv-2dudv-2(Tu+Tv)+2|Nu∩Nv|dudv-|Nu∩Nv|=du2mu+dv2mv-2(Tu+Tv)dudv-|Nu∩Nv|-2.
From Lemmas1 and 2, we have
(17)ρ(G)≤12ρ(B)+1≤max{12Ruv(N)+1:uv∈V(H)}.
It means that (14) holds and the equality in (14) holds if and only if G is a regular graph.In a graph, letα and β represent the number of vertices with the maximum degree and minimum degree, respectively. Then, we get the following results.Theorem 6.
LetG be a simple connected graph with n vertices. If Δ≤min{n-1-β,n-1-α}, then
(18)ρ(G)≤2m+Δ(δ′-1)-βδ-(n-1-β)δ′,(19)ρ(G)≥2m+(Δ′-1)δ-αΔ-(n-1-α)Δ′;
the equality holds if and only if G is a regular graph.Proof.
SinceRv(A2) is exactly the number of walks of length 2 in G with a starting point v, thus
(20)Rv(A2)=∑u~vdu=2m-dv-∑u≁vdu.
Therefore, from Lemmas1 and 3, if Δ≤n-1-β, we have dv≤n-1-β for any v∈V(G). Then
(21)ρ(A2)≤maxv∈V(G)(2m-dv-∑u≁vdu)≤maxv∈V(G)(2m-dv-(βδ+(n-dv-1-β)δ′))=maxv∈V(G)(2m+(δ′-1)dv-βδ-(n-1-β)δ′)≤2m+Δ(δ′-1)-βδ-(n-1-β)δ′.
Hence, it is easy to obtain that (18) holds.
If equality in (18) holds, then all equalities in the above argument must hold. Thus, for all v∈V(G)(22)∑u≁vdu=βδ+(n-dv-1-β)δ′.
It means thatdv=n-1 and δ′=δ, or du=δ=δ′; this shows that the graph G is regular. Conversely, if G is k-regular, it is not difficult to check that ρ(G) attains the upper bound by direct calculation.
Similarly for the lower bound, ifΔ≤n-1-α, we have
(23)ρ(A2)≥minv∈V(G)(2m-dv-∑u≁vdu)≥minv∈V(G)(2m-dv-(αΔ+(n-dv-1-α)Δ′))=minv∈V(G)(2m+(Δ′-1)dv-αΔ-(n-1-α)Δ′)≥2m+(Δ′-1)δ-αΔ-(n-1-α)Δ′.
It means that (19) holds and the equality in (19) holds if and only if G is a regular graph by similar discussion.Theorem 7.
LetG be a simple connected graph with n vertices. If Δ≤n-1-β; then
(24)ρ(G)≤δ′-1+(δ′+1)2+8m-4β(δ-δ′)-4nδ′2;
the equality holds if and only if G is a regular graph.Proof.
According to the proof of Theorem6, we have
(25)Rv(A2)=2m-dv-∑u≁vdu≤2m+(δ′-1)dv-βδ-(n-1-β)δ′.
Thus(26)Rv(A2-(δ′-1)A)≤2m-βδ-(n-1-β)δ′.
From Lemma3, we have
(27)ρ2(A)-(δ′-1)ρ(A)-2m+βδ+(n-1-β)δ′≤0.
Solving this quadratic inequality, we obtain that upper bound (24) holds.
If equality in (24) holds, then all equalities in the argument must hold. By the similar discussion of Theorem 6, the equality holds if and only if G is a regular graph.


### 2.3.  Numerical Examples

In this section, we will present two graphs to illustrate that our some new bounds are better than other bounds in some sense. Let Figures2 and 3 be graphs of orders 7 and 8.Figure 2
Graph of order 7.Figure 3
Graph of order 8.The estimated value of each upper bound is listed in Table1. Obviously, from Table 1, bound (24) is the best in all known upper bounds for Figure 2 and bound (14) is the best for Figure 3. Furthermore, bound (18) is the best except (13) and (24) for Figure 2. Hence, commonly, these upper bounds are incomparable.Table 1
Estimated value of each upper bound.
Upper bounds
Figure2
Figure3
Bound (5)
3.1623
4.1231
Bound (6)
3.1623
3.6056
Bound (7)
3.1623
3.6056
Bound (8)
3.1623
4.0000
Bound (9)
3.4641
3.8079
Bound (10)
3.6056
3.8079
Bound (11)
3.2787
3.6056
Bound (12)
3.5811
3.8028
Bound (13)
3.0650
3.6250
Bound (14)
3.5000
3.5000
Bound (18)
3.1623
4.0000
Bound (24)
3.0000
4.0000
Actual value
2.7321
3.3028


## 2.1. Previous Results

The eigenvalues of adjacency matrix of the graph have wide applications in many fields. For instance, it can be used to present the energy level of specific electrons. Specially, the spectral radius of a graph is the maximum energy level of molecules. Hence, good upper bound for the spectral radius helps to estimate the energy level of molecules [12–15]. Recently, there are some classic upper bounds for the spectral radius of graphs.In the early time Cao [16] gave a bound as follows:
(5)ρ(G)≤2m-δ(n-1)+Δ(δ-1).The equality holds if and only ifG is regular graph or a star plus of K2, or a complete graph plus a regular graph with smaller degree of vertices.Hu [17] obtained an upper bound with simple form as follows:
(6)ρ(G)≤2m-n-δ+2.The equality holds if and only ifG is n-2 regular graph.In 2005, Xu [18] proved that
(7)ρ(G)≤2m-n+1-(δ-1)(n-1-Δ).The equality holds if and only ifG is regular graph or a star graph.Using the average 2-degree of the vertices, the rese-archers got more upper bounds.Cao’s [16] another upper bound:
(8)ρ(G)≤maxu∈V(G)dumu.The equality holds if and only ifG is a regular graph or a semiregular bipartite graph.Similarly, Abrham and Zhang [19] proved that
(9)ρ(G)≤maxuv∈E(G)dudv.The equality holds if and only ifG  is a regular graph or a semiregular bipartite graph.In recent years, Feng et al. [10] give some upper bounds for the spectral radius as follows:
(10)ρ(G)≤maxu∈V(G)du2+dumu2.The equality holds if and only ifG is regular graph. 								(11)ρ(G)≤maxuv∈E(G)du(du+mu)+dv(dv+mv)2.The equality holds if and only ifG is regular graph. 								(12)ρ(G)≤maxu∈V(G)du+dumu2.The equality holds if and only ifG is regular graph. 								(13)ρ(G)≤maxuv∈E(G)du+dv+(du-dv)2+4mumv4.The equality holds if and only ifG is regular graph.


## 2.2. Main Results

All of these upper bounds mentioned in Section2.1 are characterized by the degree and the average 2-degree of the vertices. Actually, we can also use other invariants of the graph to estimate the spectral radius. In the following, such an invariant will be introduced.In a graph, a circle with length 3 is called a triangle. Ifu is a triangle’s vertex in a graph, then u is incident with this triangle. Denote by Tu the number of the triangles associated with the vertex u. For example, in Figure 1, we have Tu = 3 and Tv = Tw= 0.Figure 1
Graph with triangles.LetNu∩Nv be the set of the common adjacent points of vertex u and v; then |Nu∩Nv| present the cardinality of Nu∩Nv.Now, some new and sharp upper and lower bounds for the spectral radius will be given.Theorem 5.
LetG be a simple connected graph with n vertices. Then
(14)ρ(G)≤maxuv∈E(G)du2mu+dv2mv-2(Tu+Tv)2(dudv-|Nu∩Nv|);
the equality holds if and only if G is a regular graph.Proof.
LetK=diag(dudv-|Nu∩Nv|:uv∈E(G)) is a diagonal matrix and B is the adjacency matrix of the line graph. Denote N=K-1BK, then N and B have the same eigenvalues. Since G is a simple connected graph, it is easy to obtain that N is nonnegative and irreducible matrix. The (uv,pq)th entry of N is equal to
(15){dpdq-|Np∩Nq|dudv-|Nu∩Nv|,pq~uv,0,else,
here pq~uv implies that pq and uv are adjacent in graph. Hence, the uvth row sum Ruv(N) of N is
(16)∑pq~uvdpdq-|Np∩Nq|dudv-|Nu∩Nv|=∑q~ududq+∑p~vdpdv-2dudvdudv-|Nu∩Nv|-∑q~u|Nu∩Nq|+∑p~v|Np∩Nv|-2|Nu∩Nv|dudv-|Nu∩Nv|=du2mu+dv2mv-2dudv-2(Tu+Tv)+2|Nu∩Nv|dudv-|Nu∩Nv|=du2mu+dv2mv-2(Tu+Tv)dudv-|Nu∩Nv|-2.
From Lemmas1 and 2, we have
(17)ρ(G)≤12ρ(B)+1≤max{12Ruv(N)+1:uv∈V(H)}.
It means that (14) holds and the equality in (14) holds if and only if G is a regular graph.In a graph, letα and β represent the number of vertices with the maximum degree and minimum degree, respectively. Then, we get the following results.Theorem 6.
LetG be a simple connected graph with n vertices. If Δ≤min{n-1-β,n-1-α}, then
(18)ρ(G)≤2m+Δ(δ′-1)-βδ-(n-1-β)δ′,(19)ρ(G)≥2m+(Δ′-1)δ-αΔ-(n-1-α)Δ′;
the equality holds if and only if G is a regular graph.Proof.
SinceRv(A2) is exactly the number of walks of length 2 in G with a starting point v, thus
(20)Rv(A2)=∑u~vdu=2m-dv-∑u≁vdu.
Therefore, from Lemmas1 and 3, if Δ≤n-1-β, we have dv≤n-1-β for any v∈V(G). Then
(21)ρ(A2)≤maxv∈V(G)(2m-dv-∑u≁vdu)≤maxv∈V(G)(2m-dv-(βδ+(n-dv-1-β)δ′))=maxv∈V(G)(2m+(δ′-1)dv-βδ-(n-1-β)δ′)≤2m+Δ(δ′-1)-βδ-(n-1-β)δ′.
Hence, it is easy to obtain that (18) holds.
If equality in (18) holds, then all equalities in the above argument must hold. Thus, for all v∈V(G)(22)∑u≁vdu=βδ+(n-dv-1-β)δ′.
It means thatdv=n-1 and δ′=δ, or du=δ=δ′; this shows that the graph G is regular. Conversely, if G is k-regular, it is not difficult to check that ρ(G) attains the upper bound by direct calculation.
Similarly for the lower bound, ifΔ≤n-1-α, we have
(23)ρ(A2)≥minv∈V(G)(2m-dv-∑u≁vdu)≥minv∈V(G)(2m-dv-(αΔ+(n-dv-1-α)Δ′))=minv∈V(G)(2m+(Δ′-1)dv-αΔ-(n-1-α)Δ′)≥2m+(Δ′-1)δ-αΔ-(n-1-α)Δ′.
It means that (19) holds and the equality in (19) holds if and only if G is a regular graph by similar discussion.Theorem 7.
LetG be a simple connected graph with n vertices. If Δ≤n-1-β; then
(24)ρ(G)≤δ′-1+(δ′+1)2+8m-4β(δ-δ′)-4nδ′2;
the equality holds if and only if G is a regular graph.Proof.
According to the proof of Theorem6, we have
(25)Rv(A2)=2m-dv-∑u≁vdu≤2m+(δ′-1)dv-βδ-(n-1-β)δ′.
Thus(26)Rv(A2-(δ′-1)A)≤2m-βδ-(n-1-β)δ′.
From Lemma3, we have
(27)ρ2(A)-(δ′-1)ρ(A)-2m+βδ+(n-1-β)δ′≤0.
Solving this quadratic inequality, we obtain that upper bound (24) holds.
If equality in (24) holds, then all equalities in the argument must hold. By the similar discussion of Theorem 6, the equality holds if and only if G is a regular graph.


## 2.3.  Numerical Examples

In this section, we will present two graphs to illustrate that our some new bounds are better than other bounds in some sense. Let Figures2 and 3 be graphs of orders 7 and 8.Figure 2
Graph of order 7.Figure 3
Graph of order 8.The estimated value of each upper bound is listed in Table1. Obviously, from Table 1, bound (24) is the best in all known upper bounds for Figure 2 and bound (14) is the best for Figure 3. Furthermore, bound (18) is the best except (13) and (24) for Figure 2. Hence, commonly, these upper bounds are incomparable.Table 1
Estimated value of each upper bound.
Upper bounds
Figure2
Figure3
Bound (5)
3.1623
4.1231
Bound (6)
3.1623
3.6056
Bound (7)
3.1623
3.6056
Bound (8)
3.1623
4.0000
Bound (9)
3.4641
3.8079
Bound (10)
3.6056
3.8079
Bound (11)
3.2787
3.6056
Bound (12)
3.5811
3.8028
Bound (13)
3.0650
3.6250
Bound (14)
3.5000
3.5000
Bound (18)
3.1623
4.0000
Bound (24)
3.0000
4.0000
Actual value
2.7321
3.3028


## 3. Bounds of the Nordhaus-Gaddum Type

### 3.1. Previous Results

In this part, we mainly discuss the upper bounds on the sum of Laplacian spectral radius of a connected graphG and its complement Gc, which is called the upper bound of the Nordhaus-Gaddum type. For convenience, let
(28)σ(G)=μ(G)+μ(Gc).The following are some classic upper bounds of Nordhaus-Gaddum type. The coarse boundμ(G)≤2Δ easily implies the simplest upper bound on σ(G):
(29)σ(G)≤2(n-1)+2(Δ-δ).In particular, if bothG and Gc are connected and irregular, Shi [20] gave a better upper bound as follows:
(30)σ(G)≤2(n-1-22n2-n)+2(Δ-δ).Liu et al. [21] proved that
(31)σ(G)≤n-2+{(Δ-ω)2+n2+4(Δ-δ)(n-1)}1/2,
where ω=n-δ-1.Shi [20] gives another upper bound
(32)σ(G)≤2{(n-1)(2ω-δ)+(Δ+δ)2-Δ+δ}1/2.To learn other bounds of the Nordhaus-Gaddum type, see references [22, 23]. In order to state the main result of this section, we first give an upper bound for the Laplacian spectral radius.


### 3.2. Laplacian Spectral Radius

Here we give a new upper bound for the Laplacian spectral radius. For convenience, let(33)f(m,Δ,δ)=((Δ-δ2-1)2+16m-2δ(4n-δ-2))1/2.Theorem 8.
LetG be a simple connected graph of order n with Δ and δ; then
(34)μ(G)≤Δ+(3/2)δ-1+f(m,Δ,δ)2,
with equality holds if and only if G is bipartite regular.Proof.
LetK=Q-δE; then Rv(K)=2dv-δ, it means that 2dv=Rv(K)+δ. Considering the vth row sum of matrix K2, we have
(35)Rv(K2)=Rv(Q2)-2δRv(Q)+δ2=2dv2+2∑u~vdu-4δdv+δ2=2dv2+2(2m-dv-∑u≁v,u≠vdu)-4δdv+δ2≤2dv2+2(2m-dv-(n-dv-1)δ)-4δdv+δ2=2dv2-2dv-2δdv+4m-2(n-1)δ+δ2=(2dv-δ)dv-(2+δ)dv+4m-2(n-1)δ+δ2≤ΔRv(K)-(2+δ)Rv(K)+δ2+4m-2(n-1)δ+δ2=(Δ-δ2-1)Rv(K)+4m-2nδ+δ+δ22.
This is equivalent to the following inequality:(36)Rv(K2-(Δ-δ2-1)K)≤4m-2nδ+δ+δ22.
From Lemma3, we obtain that
(37)ρ2(K)-(Δ-δ2-1)ρ(K)≤4m-2nδ+δ+δ22.
By simple calculation, we get the upper bound of the spectral radius of matrixK as follows:
(38)ρ(K)≤Δ-(δ/2)-12+((Δ-(δ/2)-1)2+16m-2δ(4n-δ-2))1/22.
Sinceρ(K)=ρ(Q)-δ, therefore from Lemma 4 we obtain that the result (34) holds.
If the spectral radiusμ(G) achieves the upper bound in (34), then each inequality in the above proof must be equal. This implies that Δ=δ for all v∈V(G), thus G is regular graph. From Lemma 4 again, G is regular bipartite graph.
Conversely, it is easy to verify that equality in (34) holds for regular bipartite graphs.


### 3.3. Bound of the Nordhaus-Gaddum Type

In this part, based on Theorem8, an upper bound of Nordhaus-Gaddum type of Laplacian matrix will be given.Theorem 9.
LetG be a simple graph of order n with Δ and δ; then(39)σ(G)≤5n-Δ+δ-9+2{2(2Δ-δ-2)2+8δ(2+δ)+(ω-Δ)(n+3Δ-3δ-5)+32nω-8π(3n+Δ-1)}1/24here ω=n-δ-1 and π=n-Δ-1. Moreover, if both G and Gc are connected, then the upper bound is strict.Proof.
According to the relation of a graphG and its complement, it is not difficult to obtain the invariants of Gc. Denote it by Δ(Gc)=n-δ-1, δ(Gc)=n-Δ-1, and m(Gc)=Cn2-m. From Theorem 8, we have
(40)μ(Gc)≤Δ(Gc)+(3/2)δ(Gc)-12+f(m(Gc),Δ(Gc),δ(Gc))2.
Let(41)g(m)=f(m,Δ,δ)+f(m(Gc),Δ(Gc),δ(Gc)).
Then the upper bound of the Nordhaus-Gaddum type of Laplacian matrix is(42)σ(G)=μ(G)+μ(Gc)≤5n-Δ+δ-9+2g(m)4
since(43)g′(m)=8f(m,Δ,δ)-8f(m(Gc),Δ(Gc),δ(Gc)).
Obviously,g′(m)≥0 holds if and only if the following inequality holds:
(44)f(m,Δ,δ)≤f(Cn2-m,n-δ-1,n-Δ-1).
Letm be a variable; then solving this inequality, we have
(45)m≤(n-δ-Δ-1)(n-3δ+3Δ-5)+32n(n+δ-1)128-8δ(δ+2)-8(n-Δ-1)(3n+Δ-1)128=m*.
Here, the symbolm* represents the right hand of the above inequality. Then we can assert that g(m) is an increasing function for m≤m*, and it implies that g(m)≤g(m*). Therefore, we have
(46)σ(G)≤5n-Δ+δ-9+2g(m*)4=5n-Δ+δ-9+4f(m*,Δ,δ)4.
Simplifying this expression by direct calculation, we prove that the result (39) is correct.
If equality in (39) holds, then each inequality in the above proof must be equality. From Theorem 8, we obtain that both G and Gc are regular bipartite. But it is impossible for a connected graph, this implies that the Laplacian spectral radius of either G or Gc fails to achieve its upper bound and so does the sum. Hence the inequality in (39) is strict.


### 3.4. Numerical Examples

In this section, we give some examples to illustrate that the new bound is better than other bounds for some graphs. Considering the graph of order 10 in Figure4 and Figures 1–3, the estimated value of each upper bound of the Nordhaus-Gaddum type is given in Table 2.Table 2
Estimated value of each upper bound.
Upper bound
Figure1
Figure2
Figure3
Figure4
Bound (29)
28
18
16
46
Bound (30)
27.98
17.96
15
.
96
45.99
Bound (31)
26.23
16.05
15.59
46.02
Bound (32)
28.43
17.44
18.22
50.52
Bound (39)
25.84
15.88
15.52
44.97Figure 4
Graph of order 10.Clearly, from Table2, we can see that new bound (39) is the best in all known upper bounds for all figures mentioned in this paper.


## 3.1. Previous Results

In this part, we mainly discuss the upper bounds on the sum of Laplacian spectral radius of a connected graphG and its complement Gc, which is called the upper bound of the Nordhaus-Gaddum type. For convenience, let
(28)σ(G)=μ(G)+μ(Gc).The following are some classic upper bounds of Nordhaus-Gaddum type. The coarse boundμ(G)≤2Δ easily implies the simplest upper bound on σ(G):
(29)σ(G)≤2(n-1)+2(Δ-δ).In particular, if bothG and Gc are connected and irregular, Shi [20] gave a better upper bound as follows:
(30)σ(G)≤2(n-1-22n2-n)+2(Δ-δ).Liu et al. [21] proved that
(31)σ(G)≤n-2+{(Δ-ω)2+n2+4(Δ-δ)(n-1)}1/2,
where ω=n-δ-1.Shi [20] gives another upper bound
(32)σ(G)≤2{(n-1)(2ω-δ)+(Δ+δ)2-Δ+δ}1/2.To learn other bounds of the Nordhaus-Gaddum type, see references [22, 23]. In order to state the main result of this section, we first give an upper bound for the Laplacian spectral radius.


## 3.2. Laplacian Spectral Radius

Here we give a new upper bound for the Laplacian spectral radius. For convenience, let(33)f(m,Δ,δ)=((Δ-δ2-1)2+16m-2δ(4n-δ-2))1/2.Theorem 8.
LetG be a simple connected graph of order n with Δ and δ; then
(34)μ(G)≤Δ+(3/2)δ-1+f(m,Δ,δ)2,
with equality holds if and only if G is bipartite regular.Proof.
LetK=Q-δE; then Rv(K)=2dv-δ, it means that 2dv=Rv(K)+δ. Considering the vth row sum of matrix K2, we have
(35)Rv(K2)=Rv(Q2)-2δRv(Q)+δ2=2dv2+2∑u~vdu-4δdv+δ2=2dv2+2(2m-dv-∑u≁v,u≠vdu)-4δdv+δ2≤2dv2+2(2m-dv-(n-dv-1)δ)-4δdv+δ2=2dv2-2dv-2δdv+4m-2(n-1)δ+δ2=(2dv-δ)dv-(2+δ)dv+4m-2(n-1)δ+δ2≤ΔRv(K)-(2+δ)Rv(K)+δ2+4m-2(n-1)δ+δ2=(Δ-δ2-1)Rv(K)+4m-2nδ+δ+δ22.
This is equivalent to the following inequality:(36)Rv(K2-(Δ-δ2-1)K)≤4m-2nδ+δ+δ22.
From Lemma3, we obtain that
(37)ρ2(K)-(Δ-δ2-1)ρ(K)≤4m-2nδ+δ+δ22.
By simple calculation, we get the upper bound of the spectral radius of matrixK as follows:
(38)ρ(K)≤Δ-(δ/2)-12+((Δ-(δ/2)-1)2+16m-2δ(4n-δ-2))1/22.
Sinceρ(K)=ρ(Q)-δ, therefore from Lemma 4 we obtain that the result (34) holds.
If the spectral radiusμ(G) achieves the upper bound in (34), then each inequality in the above proof must be equal. This implies that Δ=δ for all v∈V(G), thus G is regular graph. From Lemma 4 again, G is regular bipartite graph.
Conversely, it is easy to verify that equality in (34) holds for regular bipartite graphs.


## 3.3. Bound of the Nordhaus-Gaddum Type

In this part, based on Theorem8, an upper bound of Nordhaus-Gaddum type of Laplacian matrix will be given.Theorem 9.
LetG be a simple graph of order n with Δ and δ; then(39)σ(G)≤5n-Δ+δ-9+2{2(2Δ-δ-2)2+8δ(2+δ)+(ω-Δ)(n+3Δ-3δ-5)+32nω-8π(3n+Δ-1)}1/24here ω=n-δ-1 and π=n-Δ-1. Moreover, if both G and Gc are connected, then the upper bound is strict.Proof.
According to the relation of a graphG and its complement, it is not difficult to obtain the invariants of Gc. Denote it by Δ(Gc)=n-δ-1, δ(Gc)=n-Δ-1, and m(Gc)=Cn2-m. From Theorem 8, we have
(40)μ(Gc)≤Δ(Gc)+(3/2)δ(Gc)-12+f(m(Gc),Δ(Gc),δ(Gc))2.
Let(41)g(m)=f(m,Δ,δ)+f(m(Gc),Δ(Gc),δ(Gc)).
Then the upper bound of the Nordhaus-Gaddum type of Laplacian matrix is(42)σ(G)=μ(G)+μ(Gc)≤5n-Δ+δ-9+2g(m)4
since(43)g′(m)=8f(m,Δ,δ)-8f(m(Gc),Δ(Gc),δ(Gc)).
Obviously,g′(m)≥0 holds if and only if the following inequality holds:
(44)f(m,Δ,δ)≤f(Cn2-m,n-δ-1,n-Δ-1).
Letm be a variable; then solving this inequality, we have
(45)m≤(n-δ-Δ-1)(n-3δ+3Δ-5)+32n(n+δ-1)128-8δ(δ+2)-8(n-Δ-1)(3n+Δ-1)128=m*.
Here, the symbolm* represents the right hand of the above inequality. Then we can assert that g(m) is an increasing function for m≤m*, and it implies that g(m)≤g(m*). Therefore, we have
(46)σ(G)≤5n-Δ+δ-9+2g(m*)4=5n-Δ+δ-9+4f(m*,Δ,δ)4.
Simplifying this expression by direct calculation, we prove that the result (39) is correct.
If equality in (39) holds, then each inequality in the above proof must be equality. From Theorem 8, we obtain that both G and Gc are regular bipartite. But it is impossible for a connected graph, this implies that the Laplacian spectral radius of either G or Gc fails to achieve its upper bound and so does the sum. Hence the inequality in (39) is strict.


## 3.4. Numerical Examples

In this section, we give some examples to illustrate that the new bound is better than other bounds for some graphs. Considering the graph of order 10 in Figure4 and Figures 1–3, the estimated value of each upper bound of the Nordhaus-Gaddum type is given in Table 2.Table 2
Estimated value of each upper bound.
Upper bound
Figure1
Figure2
Figure3
Figure4
Bound (29)
28
18
16
46
Bound (30)
27.98
17.96
15
.
96
45.99
Bound (31)
26.23
16.05
15.59
46.02
Bound (32)
28.43
17.44
18.22
50.52
Bound (39)
25.84
15.88
15.52
44.97Figure 4
Graph of order 10.Clearly, from Table2, we can see that new bound (39) is the best in all known upper bounds for all figures mentioned in this paper.


## 4. Conclusion

From numerical examples of Sections2 and 3, the estimated value of new upper bounds of the spectral radius and the Nordhaus-Gaddum type of graphs are the smallest in all known upper bounds for the graphs considered in these examples. It means that our results are better than the existing upper bounds in some sense.



---

*Source: 472956-2013-06-05.xml*