Signless Laplacian Spectral Conditions for Hamiltonicity of Graphs

Abstract

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

(ProQuest: ... denotes non-US-ASCII text omitted.)

Guidong Yu 1 and Miaolin Ye 1 and Gaixiang Cai 1 and Jinde Cao 2, 3

Academic Editor:Francesco Soldovieri

1, School of Mathematics & Computation Sciences, Anqing Normal College, Anqing 246011, China
2, Department of Mathematics, Southeast University, Nanjing, Jiangsu 210096, China
3, Department of Mathematics, Faculty of Science, King Abdulaziz University, Jeddah 21589, Saudi Arabia

Received 23 January 2014; Revised 7 June 2014; Accepted 16 June 2014; 30 June 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 of G 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)...4;k-1 for any pair of nonadjacent vertices x∈X and y∈Y of _Ck (_GBPT ) .

Lemma 1 (see [9]).

Let _GBPT =(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r...5;2 . Then, _GBPT is Hamiltonian if and only if _Cr+1 (_GBPT ) is Hamiltonian.

For a graph G , 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]).

Let G be a graph with at least one edge. Then, [figure omitted; refer to PDF] if and only if G is regular or semi-regular.

Let M be a Hermitian matrix of order n , and let _λ1 (M)...5;_λ2 (M)...5;......5;_λn (M) be the eigenvalues of M .

Lemma 3 (see [10]).

Let B and C be Hermitian matrices of order n , 1...4;i , j...4;n . Then, [figure omitted; refer to PDF] if i+j...4;n+1 .

Lemma 4.

Let G be a graph. Then, [figure omitted; refer to PDF]

Proof.

Because Q(G)=A(G)+D(G) , by Lemma 3, [figure omitted; refer to PDF] We notice that _λ1 (A(G))=μ(G) , _λ1 (D(G))=Δ(G) , and _λ1 (Q(G))=q(G) . So, the result follows.

Let _GBPT =(X,Y;E) be a bipartite graph, the quasi-complement of _GBPT is denoted by ^GBPT* ...=(X,Y;^{E[variant prime]} ) , where ^{E[variant prime]} ={xy:x∈X,y∈Y,xy∉E} .

Theorem 5.

Let _GBPT =(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r...5;2 . If [figure omitted; refer to PDF] then _GBPT is Hamiltonian.

Proof.

Suppose that _GBPT 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)...4;r for any pair of nonadjacent vertices x∈X and y∈Y in _HBPT . So, [figure omitted; refer to PDF] for any pair of adjacent vertices x∈X , y∈Y in ^HBPT* . Hence, [figure omitted; refer to PDF]

By Lemma 2, we have that [figure omitted; refer to PDF]

As ^HBPT* is a subgraph of ^GBPT* , by Perron-Frobenius theorem, [figure omitted; refer to PDF]

Thus, by (5), (8), and (9), we have that [figure omitted; refer to PDF] a contradiction.

Li [4] has given a sufficient condition for a bipartite graph to be Hamiltonian as follows.

Theorem 6 (see [4]).

Let _GBPT =(X,Y;E) be a connected balanced bipartite graph, where |X|=|Y|=r...5;2 . If [figure omitted; refer to PDF] then _GBPT is Hamiltonian.

Remark 7.

We now compare Theorems 5 and 6. If μ(^GBPT* )...4;(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...5;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

Write _Kn-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 [congruent with]...[congruent with]_Gk , we write k_G1 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]).

Let G be a connected graph of order n...5;4 . If [figure omitted; refer to PDF] then G is traceable unless G[congruent with]_K1 ⋁(_Kn-3 ∪2_K1 ) , _K2 ⋁(3_K1 ∪_K2 ) , or _K4 ⋁(6_K1 ) .

Let G 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]).

Let G be a graph of order n . Then, [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] with equality if and only if G is a regular graph or a semi-regular graph.

In fact, if G is disconnected, there exists a component H of G such that [figure omitted; refer to PDF] 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.

Let G be a graph of order n . Then, [figure omitted; refer to PDF] 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 graph G of order n , a vector X∈^Rn is called a function defined on G , if there is a 1-1 map [straight phi] from V(G) to the entries of X , simply written as _Xu =[straight phi](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 [figure omitted; refer to PDF] where _NG (v) denotes the neighborhood of v in G . The equation (17) is called (q,X) -eigenequation of G .

Theorem 12.

Let G be a connected graph of order n...5;4 . If [figure omitted; refer to PDF] then G is traceable.

Proof.

By Corollary 11 and (18), we have [figure omitted; refer to PDF]

Suppose that G is non-traceable. Then, by Lemma 8 and (19), G[congruent with]_K1 ⋁(_Kn-3 ∪2_K1 ) , _K2 ⋁(3_K1 ∪_K2 ) , or _K4 ⋁(6_K1 ) .

If G[congruent with]_K1 ⋁(_Kn-3 ∪2_K1 ) , let X=^{(_X1 ,_X2 ,...,_Xn )T} be the eigenvector of Q(G) corresponding to eigenvalue q(G) . By (18), we know that q(G)...0;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 [figure omitted; refer to PDF] Transform (20) into a matrix equation (B-q(G)I)^{X[variant prime]} =0 , where ^{X[variant prime]} =^{(_X1 ,_X2 ,_X3 )T} and [figure omitted; refer to PDF]

Thus, q(G) is the largest root of the following equation: [figure omitted; refer to PDF] Let f(x)=^x3 +(-3n+7)^x2 +(2ⁿ² -7n)x-2ⁿ² +14n-24 ; then ^{f[variant prime]} (x)=3^x2 +2(-3n+7)x+2ⁿ² -7n . Let ^{f[variant prime]} (x)=0 ; we have two values _x1 and _x2 , such that ^{f[variant prime]} (_x1 )=^{f[variant prime]} (_x2 )=0 , where [figure omitted; refer to PDF]

Hence, f(x) is strictly increasing with respect to x for x>_x2 .

Because f(2(n-3))=2ⁿ² -17n+33>0 and (2(n-2⁾² +4)/(n-1)>2(n-3)>_x2 , we have that f((2(n-2⁾² +4)/(n-1))>0 , which implies that q(G)<(2(n-2⁾² +4)/(n-1) .

If G[congruent with]_K2 ⋁(3_K1 ∪_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)...0;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 [figure omitted; refer to PDF] Transform (24) into a matrix equation (B-q(G)I)^{X[variant prime]} =0 , where ^{X[variant prime]} =^{(_X1 ,_X2 ,_X3 )T} and [figure omitted; refer to PDF]

Thus, q(G) is the largest root of the following equation: [figure omitted; refer to PDF] Let g(x)=^x3 -13^x2 +40x-24 ; we can easily get that g(x) is strictly increasing with respect to x for x>20/3 .

Consider g(9)=12>0 , which implies that q(G)<9 .

If G[congruent with]_K4 ⋁(6_K1 ) , 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]).

Let G be a connected graph of order n...5;5 . If [figure omitted; refer to PDF] then G is traceable.

Example 14.

There are graphs to which Theorem 12 may apply but Theorem 13 may not. Let G=(_Kr ∪_Kr )⋁_K1 of order n...=2r+1 , where r...5;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, [figure omitted; refer to PDF] 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 graph G of order n , Erdös and Gallai [14] prove that if [figure omitted; refer to PDF] 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)...4;k-1 for any pair of nonadjacent vertices u∈V and v∈V of _Ck (G) .

Lemma 15 (see [7]).

Let G be a graph of order n . Then, G is Hamilton-connected if and only if _Cn+1 (G) is Hamilton-connected.

Lemma 16.

Let G be a simple graph with degree sequence (_dG (_v1 ),_dG (_v2 ),...,_dG (_vn )) , where _dG (_v1 )...4;_dG (_v2 )...4;......4;_dG (_vn ) and n...5;3 . Suppose that there is no integer k...4;n/2 such that _dG (_vk-1 )...4;k and _dG (_vn-k )...4;n-k . Then, G is Hamilton-connected.

Proof.

Let H-=_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 [figure omitted; refer to PDF] and _dH- (u)+_dH- (v) being as large as possible. By the definition of _Cn+1 (G) , we have [figure omitted; refer to PDF] 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, [figure omitted; refer to PDF] 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)...5;_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 )...4;k and _dG (_vn-k )...4;n-k . Because k...4;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 write _Kn-1 +e+^{e[variant prime]} for _Kn-1 together with a vertex joining two vertices of _Kn-1 by edges e,^{e[variant prime]} , respectively.

Lemma 17.

Let G be a connected graph of order n...5;6 . If [figure omitted; refer to PDF] then G is Hamilton-connected unless G[congruent with]_Kn-1 +e+^{e[variant prime]} or G[congruent with]_O3 ⋁_K3 .

Proof.

Suppose that G is not a Hamilton-connected graph with degree sequence (_dG (_v1 ),_dG (_v2 ),...,_dG (_vn )) , where _dG (_v1 )...4;_dG (_v2 )...4;......4;_dG (_vn ) and n...5;6 . By Lemma 16, there is integer k...4;n/2 such that _dG (_vk-1 )...4;k and _dG (_vn-k )...4;n-k . Since G is connected, k...5;2 . Thus, [figure omitted; refer to PDF]

Because 2...4;k...4;n/2 , (9-2n)/6...4;k-(2n+3)/6...4;(n-3)/6 . Thus, if n...5;6 , [figure omitted; refer to PDF] Since e(G)...5;(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[congruent with]_Kn-1 +e+^{e[variant prime]} . 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[congruent with]_O3 ⋁_K3 .

Theorem 18.

Let G be a connected graph of order n...5;6 . If [figure omitted; refer to PDF] then G is Hamilton-connected.

Proof.

By Corollary 11 and (36), we have [figure omitted; refer to PDF]

Suppose that G is not Hamilton-connected. Then, by Lemma 17 and (37), G[congruent with]_Kn-1 +e+^{e[variant prime]} or G[congruent with]_O3 ⋁_K3 .

If G[congruent with]_Kn-1 +e+^{e[variant prime]} . 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)...0;n-3 and q(G)...0;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 [figure omitted; refer to PDF] Transform (38) into a matrix equation (B-q(G)I)^{X[variant prime]} =0 , where ^{X[variant prime]} =^{(_X1 ,_X2 ,_X3 )T} and [figure omitted; refer to PDF]

Thus, q(G) is the largest root of following equation: [figure omitted; refer to PDF]

Let f(x)=^x3 +(4-3n)^x2 +(2ⁿ² -2n-8)x-4ⁿ² +20n-24 ; then ^{f[variant prime]} (x)=3^x2 +2(4-3n)x+2ⁿ² -2n-8 . Let ^{f[variant prime]} (x)=0 ; we have two values _x1 and _x2 , such that ^{f[variant prime]} (_x1 )=^{f[variant prime]} (_x2 )=0 , where [figure omitted; refer to PDF]

Hence, f(x) is strictly increasing with respect to x for x>_x2 .

Consider f(2(n-2)+4/(n-1))=4^(n-3)2 (ⁿ² -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) .

If G[congruent with]_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.

Acknowledgments

This work is jointly supported by the National Natural Science Foundation of China under Grant nos. 11071001 and 11071002, the Natural Science Foundation of Anhui Province of China under Grant no. 11040606M14, the Natural Science Foundation of Department of Education of Anhui Province of China under Grant nos. KJ2011A195 and KJ2013A196, and the Young Scientific Research Foundation of Anqing Normal College, no. KJ201307.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] M. Fiedler, V. Nikiforov, "Spectral radius and Hamiltonicity of graphs," Linear Algebra and Its Applications , vol. 432, no. 9, pp. 2170-2173, 2010.

[2] B. Zhou, "Signless Laplacian spectral radius and Hamiltonicity," Linear Algebra and Its Applications , vol. 432, no. 2-3, pp. 566-570, 2010.

[3] M. Lu, H. Q. Liu, F. Tian, "Spectral radius and Hamiltonian graphs," Linear Algebra and Its Applications , vol. 437, no. 7, pp. 1670-1674, 2012.

[4] R. Li, "Egienvalues, Laplacian Eigenvalues, and some Hamiltonian properties of graphs," Utilitas Mathematica , vol. 88, pp. 247-257, 2012.

[5] S. Butler, F. Chung, "Small spectral gap in the combinatorial Laplacian implies Hamiltonian," Annals of Combinatorics , vol. 13, no. 4, pp. 403-412, 2010.

[6] Y. Z. Fan, G. D. Yu, "Spectral condition for a graph to be Hamiltonian with respect to normalized Laplacian," http://arxiv.org/abs/1207.6824

[7] J. A. Bondy, V. Chvatal, "A method in graph theory," Discrete Mathematics , vol. 15, no. 2, pp. 111-135, 1976.

[8] G. Hendry, "Extending cycles in bipartite graphs," Journal of Combinatorial Theory B , vol. 51, no. 2, pp. 292-313, 1991.

[9] V. Chvátal, "On the Hamilton's ideal's," Journal of Combinatorial Theory B , vol. 12, pp. 163-168, 1972.

[10] W. So, "Commutativity and spectra of Hermitian matrices," Linear Algebra and Its Applications , vol. 212-213, no. 15, pp. 121-129, 1994.

[11] K. Ch. Das, "The Laplacian spectrum of a graph," Computers & Mathematics with Applications , vol. 48, no. 5-6, pp. 715-724, 2004.

[12] K. Ch. Das, "Maximizing the sum of the squares of the degrees of a graph," Discrete Mathematics , vol. 285, no. 1-3, pp. 57-66, 2004.

[13] L. H. Feng, G. H. Yu, "On three conjectures involving the signless Laplacian spectral radius of graphs," Publications de l'Institut Mathematique , vol. 85, no. 99, pp. 35-38, 2009.

[14] P. Erdös, T. Gallai, "On maximal paths and circuits of graphs," Acta Mathematica Hungarica , vol. 10, no. 3, pp. 337-356, 1959.