# Signless Laplacian Spectral Conditions for Hamiltonicity of Graphs

Authors: Guidong Yu; Miaolin Ye; Gaixiang Cai; Jinde Cao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We establish some signless Laplacian spectral radius conditions for a
graph to be Hamiltonian or traceable or Hamilton-connected.


---

## Body

## 1. Introduction

Let a graph,G=(V,E) be a simple graph of order n with vertex set V={v1,v2,…,vn} and edge set E. Denote by e(G)∶=|E| the number of edges of the graph G. Write by Kn a complete graph of order n, On an empty graph of order n (without edges), and Kn,m a complete bipartite graph with two parts having n, m vertices, respectively. The graph G is said to be Hamiltonian, if it has a Hamiltonian cycle which is a cycle of order n contained in G. The graph G is said to be traceable if it has a Hamiltonian path which is a path of order n contained in G. The problem of deciding whether a graph is Hamiltonian is Hamiltonian problem, which is one of the most difficult classical problems in graph theory. Indeed, it is NP-complete problem.The adjacency matrix ofG is defined to be a matrix A(G)=[aij]n×n, where aij=1 if vi is adjacent to vj and aij=0 otherwise. The largest eigenvalue of A(G) is called to be the spectral radius of G, which is denoted by μ(G). The degree matrix of G is written by D(G)=diag⁡(dG(v1),dG(v2),…,dG(vn)), where dG(vi)(i=1,2,…,n) denotes the degree of the vertex vi in the graph G. The signless Laplacian matrix of G is defined by Q(G)=D(G)+A(G). The largest eigenvalue of Q(G) is called to be the signless Laplacian spectral radius of G, which is denoted by q(G).Recently, using spectral graph theory to study the Hamiltonian problem has received a lot of attention. Some spectral conditions for a graph to be Hamiltonian or traceable have been given in [1–6]. In this paper, we still study the Hamiltonicity of a graph. Firstly, we present a signless Laplacian spectral radius condition for a bipartite graph to be Hamiltonian in Section 2. Secondly, we give some signless Laplacian spectral radius conditions for a graph to be traceable or Hamilton-connected in Section 3 and Section 4, respectively.


## 2. Signless Laplacian Spectral Radius in Hamiltonian Bipartite Graphs

The definition of the closure of a balanced bipartite graph can be found in [7, 8]. For a positive integer k, the k-closure of a balanced bipartite graph GBPT∶=(X,Y;E), where |X|=|Y|, written by Ck(GBPT), is a graph obtained from GBPT by successively joining pairs of nonadjacent vertices x∈X and y∈Y, whose degree sum is at least k, until no such pairs remain. By the definition of the Ck(GBPT), we have that dCk(GBPT)(x)+dCk(GBPT)(y)≤k-1 for any pair of nonadjacent vertices x∈X and y∈Y of Ck(GBPT).Lemma 1 (see [9]).
LetGBPT=(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r≥2. Then, GBPT is Hamiltonian if and only if Cr+1(GBPT) is Hamiltonian.For a graphG, write Z(G)∶=∑uv∈E(G)‍(dG(u)+dG(v))=∑u∈V(G)‍dG2(u), and let Δ(G) be maximum degree of G. A regular graph is a graph for which every vertex in the graph has the same degree. A semi-regular graph is a bipartite graph for which every vertex in the same partite set has the same degree.Lemma 2 (see [2]).
LetG be a graph with at least one edge. Then,
(1)q(G)≥Z(G)e(G),
if and only if G is regular or semi-regular.LetM be a Hermitian matrix of order n, and let λ1(M)≥λ2(M)≥⋯≥λn(M) be the eigenvalues of M.Lemma 3 (see [10]).
LetB and C be Hermitian matrices of order n, 1≤i, j≤n. Then,
(2)λi(B)+λj(C)≥λi+j-1(B+C),
if i+j≤n+1.Lemma 4.
LetG be a graph. Then,
(3)q(G)≤μ(G)+Δ(G).Proof.
BecauseQ(G)=A(G)+D(G), by Lemma 3,
(4)λ1(A(G))+λ1(D(G))≥λ1(Q(G)).
We notice that λ1(A(G))=μ(G), λ1(D(G))=Δ(G), and λ1(Q(G))=q(G). So, the result follows.LetGBPT=(X,Y;E) be a bipartite graph, the quasi-complement of GBPT is denoted by GBPT*∶=(X,Y;E′), where E′={xy:x∈X,y∈Y,xy∉E}.Theorem 5.
LetGBPT=(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r≥2. If
(5)q(GBPT*)<r,
then GBPT is Hamiltonian.Proof.
Suppose thatGBPT is not Hamiltonian. Then, HBPT∶=Cr+1(GBPT) is not Hamiltonian too by Lemma 1, and therefore, HBPT is not Kr,r. Thus, there exists a vertex x∈X and a vertex y∈Y such that xy∉E(HBPT). We find that dHBPT(x)+dHBPT(y)≤r for any pair of nonadjacent vertices x∈X and y∈Y in HBPT. So,
(6)dHBPT*(x)+dHBPT*(y)=r-dHBPT(x)+r-dHBPT(y)≥r,
for any pair of adjacent vertices x∈X, y∈Y in HBPT*. Hence,
(7)Z(HBPT*)=∑xy∈E(HBPT*)‍(dHBPT*(x)+dHBPT*(y))≥re(HBPT*).
By Lemma2, we have that
(8)q(HBPT*)≥Z(HBPT*)e(HBPT*)≥r.
AsHBPT* is a subgraph of GBPT*, by Perron-Frobenius theorem,
(9)q(GBPT*)≥q(HBPT*).
Thus, by (5), (8), and (9), we have that
(10)r>q(GBPT*)≥q(HBPT*)≥Z(HBPT*)e(HBPT*)≥r,
a contradiction.Li [4] has given a sufficient condition for a bipartite graph to be Hamiltonian as follows.Theorem 6 (see [4]).
LetGBPT=(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r≥2. If
(11)μ(GBPT*)≤r-22,
then GBPT is Hamiltonian.Remark 7.
We now compare Theorems5 and 6. If μ(GBPT*)≤(r-2)/2 and Δ(GBPT*)<r-(r-2)/2, we have that q(GBPT*)<r by Lemma 4. Hence Theorem 5 improves Theorem 6 when Δ(GBPT*)<r-(r-2)/2. For example, let GBPT be a regular connected balanced bipartite graph with degree (r+1)/2, where r is odd and |X|=|Y|=r≥6. Then, its quasi-complement GBPT* is a regular graph with degrees (r-1)/2, μ(GBPT*)=(r-1)/2, and q(GBPT*)=r-1. GBPT satisfies the condition of Theorems 5, and hence, it is Hamiltonian. But it does not satisfy the condition of Theorem 6.


## 3. Signless Laplacian Spectral Radius in Traceable Graphs

WriteKn-1+v for Kn-1 together with an isolated vertex. Let G=(V(G),E(G)) and H=(V(H),E(H)) be two disjoint graphs. The disjoint union of G and H, denoted by G∪H, is the graph with vertex set V(G)∪V(H) and edge set E(G)∪E(H). If G1≅⋯≅Gk, we write kG1 for G1∪⋯∪Gk. The join of G and H, denoted by G∨H, is the graph obtained from G∪H by adding edges joining every vertex of G to every vertex of H.Lemma 8 (see [3]).
LetG be a connected graph of order n≥4. If
(12)e(G)≥(n-2)(n-3)2+2,
then G is traceable unless G≅K1∨(Kn-3∪2K1), K2∨(3K1∪K2), or K4∨(6K1).LetG be a graph containing a vertex v. Denote mG(v)=m(v)=(1/dG(v))∑u∈NG(v)‍dG(u) if dG(v)>0 and mG(v)=0 otherwise, where NG(v) or simply N(v) denotes the neighborhood of v in G.Lemma 9 (see [11]).
LetG be a graph of order n. Then,
(13)max⁡{dG(v)+mG(v):v∈V(G)}≤2e(G)n-1+n-2,
with equality if and only if G⊇K1,n-1 or G=Kn-1+v.Lemma 10 (see [12]).
Let G be a connected graph. Then(14)q(G)≤max⁡{dG(v)+mG(v):v∈V(G)},
with equality if and only if G is a regular graph or a semi-regular graph.In fact, ifG is disconnected, there exists a component H of G such that
(15)q(G)=q(H)≤max⁡{dH(v)+mH(v):v∈V(H)}≤max⁡{dG(v)+mG(v):v∈V(G)}.
So the inequality (14) also holds when G is a disconnected graph. By Lemmas 9 and 10, we have the following result; also see [13].Corollary 11.
LetG be a graph of order n. Then,
(16)q(G)≤2e(G)n-1+n-2.
If G is connected, then the equality in (16) holds if and only if G=K1,n-1 or G=Kn. Otherwise, the equality in (16) holds if and only if G=Kn-1+v.Given a graphG of order n, a vector X∈Rn is called a function defined on G, if there is a 1-1 map φ from V(G) to the entries of X, simply written as Xu=φ(u) for each u∈V(G), Xu is also called the value of u given by X. If X is an eigenvector of Q(G) corresponding to the eigenvalue q, then X is defined naturally on G; that is, Xu is the entry of X corresponding to the vertex u. One can find that
(17)[q-dG(v)]Xv=∑u∈NG(v)‍Xu,foreachv∈V(G),
where NG(v) denotes the neighborhood of v in G. The equation (17) is called (q,X)-eigenequation of G.Theorem 12.
LetG be a connected graph of order n≥4. If
(18)q(G)≥2(n-2)2+4n-1,
then G is traceable.Proof.
By Corollary11 and (18), we have
(19)e(G)≥(n-1)q(G)-(n-1)(n-2)2≥(n-2)(n-3)2+2.
Suppose thatG is non-traceable. Then, by Lemma 8 and (19), G≅K1∨(Kn-3∪2K1), K2∨(3K1∪K2), or K4∨(6K1).
IfG≅K1∨(Kn-3∪2K1), let X=(X1,X2,…,Xn)T be the eigenvector of Q(G) corresponding to eigenvalue q(G). By (18), we know that q(G)≠1, n-4. Thus, by (17), all vertices of degree 1 have the same values given by X, say X1; all vertices of degree n-3 have the same values by X, say X2. Denote by X3 the value of the vertex of degree n-1 given by X. Also, by (17), we have
(20)(q(G)-1)X1=X3,(q(G)-(n-3))X2=(n-4)X2+X3,(q(G)-(n-1))X3=2X1+(n-3)X2.
Transform (20) into a matrix equation (B-q(G)I)X′=0, where X′=(X1,X2,X3)T and
(21)B=[10102n-712n-3n-1].
Thus,q(G) is the largest root of the following equation:
(22)q3+(-3n+7)q2+(2n2-7n)q-2n2+14n-24=0.
Let f(x)=x3+(-3n+7)x2+(2n2-7n)x-2n2+14n-24; then f′(x)=3x2+2(-3n+7)x+2n2-7n. Let f′(x)=0; we have two values x1 and x2, such that f′(x1)=f′(x2)=0, where
(23)x1=3n-7-3n2-21n+493,x2=3n-7+3n2-21n+493.
Hence,f(x) is strictly increasing with respect to x for x>x2.
Becausef(2(n-3))=2n2-17n+33>0 and (2(n-2)2+4)/(n-1)>2(n-3)>x2, we have that f((2(n-2)2+4)/(n-1))>0, which implies that q(G)<(2(n-2)2+4)/(n-1).
IfG≅K2∨(3K1∪K2), let X=(X1,X2,…,X7)T be the eigenvector of Q(G) corresponding to eigenvalue q(G). By (18), we know that q(G)≠2,5. Thus, by (17), three vertices of degree 2 have the same values given by X, say X1; two vertices of degree 3 have the same values, say X2; two vertices of degree 6 have the same values, say X3. Also, by (17), we have
(24)(q(G)-2)X1=2X3,(q(G)-3)X2=X2+2X3,(q(G)-6)X3=3X1+2X2+X3.
Transform (24) into a matrix equation (B-q(G)I)X′=0, where X′=(X1,X2,X3)T and
(25)B=[202042327].
Thus,q(G) is the largest root of the following equation:
(26)q3-13q2+40q-24=0.
Let g(x)=x3-13x2+40x-24; we can easily get that g(x) is strictly increasing with respect to x for x>20/3.
Considerg(9)=12>0, which implies that q(G)<9.
IfG≅K4∨(6K1), we easily calculate q(G)=8+210<44/3.
Thus, in either case, we have a contradiction.Lu et al. [3] have given a sufficient condition for a graph to be traceable as follows.Theorem 13 (see [3]).
LetG be a connected graph of order n≥5. If
(27)μ(G)≥(n-3)2+2,
then G is traceable.Example 14.
There are graphs to which Theorem12 may apply but Theorem 13 may not. Let G=(Kr∪Kr)∨K1 of order n∶=2r+1, where r≥4. Surely, the graph G is traceable. By a little computation, μ(G) is the largest root of the polynomial f(x)=x[x-(r-1)]-2r and q(G) is the largest root of the polynomial g(x)=[x-(2r-1)](x-2r)-2r. Hence,
(28)μ(G)=r+1+r2+6r+12<4r2-8r+6=(n-3)2+2,q(G)=4r-14>(2r-1)2+2r=2(n-2)2+4n-1.
So, we can apply Theorem 12 but not Theorem 13 for G to be traceable.


## 4. Signless Laplacian Spectral Radius in Hamilton-Connected Graphs

For a graphG of order n, Erdös and Gallai [14] prove that if
(29)dG(u)+dG(v)≥n+1,
for any pair of nonadjacent vertices u and v, then G is Hamilton-connected.The idea for the closure of a graph can be found in [7]. For a positive integer k, the k-closure of a graph G=(V,E), denoted by Ck(G), is a graph obtained from G by successively joining pairs of nonadjacent vertices u∈V and v∈V, whose degree sum is at least k until no such pairs remain. By the definition of the k-closure of G, we have that dCk(G)(u)+dCk(G)(v)≤k-1 for any pair of nonadjacent vertices u∈V and v∈V of Ck(G).Lemma 15 (see [7]).
LetG be a graph of order n. Then, G is Hamilton-connected if and only if Cn+1(G) is Hamilton-connected.Lemma 16.
LetG be a simple graph with degree sequence (dG(v1),dG(v2),…,dG(vn)), where dG(v1)≤dG(v2)≤⋯≤dG(vn) and n≥3. Suppose that there is no integer k≤n/2 such that dG(vk-1)≤k and dG(vn-k)≤n-k. Then, G is Hamilton-connected.Proof.
LetH-=Cn+1(G) be the (n+1)-closure of G. Next, we will prove that H- is a complete graph; then the result follows according to (29). To the contrary, suppose that H- is not a complete graph, and let u and v be two nonadjacent vertices in H- with
(30)dH-(u)≤dH-(v)
and dH-(u)+dH-(v) being as large as possible. By the definition of Cn+1(G), we have
(31)dH-(u)+dH-(v)≤n.
Denote by S the set of vertices in V∖{v} which are nonadjacent to v in H-. Denote by T the set of vertices in V∖{u} which are nonadjacent to u in H-. Then,
(32)|S|=n-1-dH-(v),|T|=n-1-dH-(u).
Furthermore, by dH-(u)+dH-(v) being as large as possible, each vertex in S has degree at most dH-(u) and each vertex in T∪{u} has degree at most dH-(v). Let k∶=dH-(u). According to (31) and (32), we have that |S|=n-1-dH-(v)≥dH-(u)-1=k-1, |T|+1=n-1-dH-(u)+1=n-dH-(u)=n-k. Then H- has at least k-1 vertices of degree not exceeding k and at least n-k vertices of degree not exceeding n-k. Because G is a spanning subgraph of H-, the same is true for G; that is, dG(vk-1)≤k and dG(vn-k)≤n-k. Because k≤n/2 by (30) and (31), this is contrary to the hypothesis. So we have that the (n+1)-closure H- of G is indeed complete graph and hence that G is Hamilton-connected by (29).We writeKn-1+e+e′ for Kn-1 together with a vertex joining two vertices of Kn-1 by edges e,e′, respectively.Lemma 17.
LetG be a connected graph of order n≥6. If
(33)e(G)≥(n-1)(n-2)2+2,
then G is Hamilton-connected unless G≅Kn-1+e+e′ or G≅O3∨K3.Proof.
Suppose thatG is not a Hamilton-connected graph with degree sequence (dG(v1),dG(v2),…,dG(vn)), where dG(v1)≤dG(v2)≤⋯≤dG(vn) and n≥6. By Lemma 16, there is integer k≤n/2 such that dG(vk-1)≤k and dG(vn-k)≤n-k. Since G is connected, k≥2. Thus,
(34)e(G)=12∑i=1n‍dG(vi)≤12[(k-1)k+(n-2k+1)(n-k)+k(n-1)]=12(n2-2nk+3k2-3k+n)=8n2-924+32(k-2n+36)2.
Because2≤k≤n/2, (9-2n)/6≤k-(2n+3)/6≤(n-3)/6. Thus, if n≥6,
(35)e(G)≤8n2-924+32(k-2n+36)2≤(n-1)(n-2)2+2.
Since e(G)≥(n-1)(n-2)/2+2, then all inequalities in the above argument should be equalities. From the last equality in (35), we have k=2 or k=3 and n=6. If k=2, by the equality in (34), G is a graph with dG(v1)=2,dG(v2)=dG(v3)=⋯=dG(vn-2)=n-2,dG(vn-1)=dG(vn)=n-1, which implies G≅Kn-1+e+e′. If k=3 and n=6, by the equality in (34), G is a graph with dG(v1)=dG(v2)=dG(v3)=3,dG(v4)=dG(v5)=dG(v6)=5, which implies G≅O3∨K3.Theorem 18.
LetG be a connected graph of order n≥6. If
(36)q(G)≥2(n-2)+4n-1,
then G is Hamilton-connected.Proof.
By Corollary11 and (36), we have
(37)e(G)≥q(G)(n-1)-(n-1)(n-2)2≥(n-1)(n-2)2+2.
Suppose thatG is not Hamilton-connected. Then, by Lemma 17 and (37), G≅Kn-1+e+e′ or G≅O3∨K3.
IfG≅Kn-1+e+e′. Let X=(X1,X2,…,Xn)T be the eigenvector of Q(G) corresponding to the eigenvalue q(G). By (36), we know that q(G)≠n-3 and q(G)≠n-2. Thus, by (17), all vertices of degree n-2 have the same values given by X, say X1, and all vertices of degree n-1 have the same values, say X2. Denote by X3 the value of the vertex of degree 2 given by X. Also, by (17), we have
(38)(q(G)-(n-2))X1=(n-4)X1+2X2,(q(G)-(n-1))X2=(n-3)X1+X2+X3(q(G)-2)X3=2X2.
Transform (38) into a matrix equation (B-q(G)I)X′=0, where X′=(X1,X2,X3)T and
(39)B=[2n-620n-3n1022].
Thus,q(G) is the largest root of following equation:
(40)q3+(4-3n)q2+(2n2-2n-8)q-4n2+20n-24=0.
Letf(x)=x3+(4-3n)x2+(2n2-2n-8)x-4n2+20n-24; then f′(x)=3x2+2(4-3n)x+2n2-2n-8. Let f′(x)=0; we have two values x1 and x2, such that f′(x1)=f′(x2)=0, where
(41)x1=3n-4-3n2-18n+403,x2=3n-4+3n2-18n+403.
Hence,f(x) is strictly increasing with respect to x for x>x2.
Considerf(2(n-2)+4/(n-1))=4(n-3)2(n2-3n+6)/(n-1)3>0 and 2(n-2)+4/(n-1)>x2, which implies that q(G)<2(n-2)+4/(n-1).
IfG≅O3∨K3. We can calculate that q(G)=5+13<8.8=2(6-2)+4/(6-1). Thus, in either case, we have a contradiction.



---

*Source: 282053-2014-06-30.xml*