# Sufficient Conditions for Hamiltonicity of Graphs with Respect to Wiener Index, Hyper-Wiener Index, and Harary Index

Authors: Guisheng Jiang; Lifang Ren; Guidong Yu
Journal: Journal of Chemistry
 (2019)

---

## Abstract

In this paper, with respect to the Wiener index, hyper-Wiener index, and Harary index, it gives some sufficient conditions for some graphs to be traceable, Hamiltonian, Hamilton-connected, or traceable for every vertex. Firstly, we discuss balanced bipartite graphs withδG≥t, where δG is the minimum degree of G, and gain some sufficient conditions for the graphs to be traceable or Hamiltonian, respectively. Secondly, we discuss nearly balanced bipartite graphs with δG≥t and present some sufficient conditions for the graphs to be traceable. Thirdly, we discuss graphs with δG≥t and obtain some conditions for the graphs to be traceable or Hamiltonian, respectively. Finally, we discuss t-connected graphs and provide some conditions for the graphs to be Hamilton-connected or traceable for every vertex, respectively.


---

## Body

## 1. Introduction

We consider only a simple graph. For a graphG=VG,EG, we use n to denote VG and eG to EG. We write dGx,y as the minimum length of the paths between x and y in G, which is called the distance between two vertices x and y of G. Denote δG=mindGv,v∈VG. For a bipartite graph G=X,Y;E, if X=Y, it is called a balanced bipartite graph; if X=Y+1, it is called a nearly balanced bipartite graph. For disjoint graphs G1 and G2, the graph G1+G2 is called the union of G1 and G2, where VG1+G2=VG1∪VG2 and EG1+G2=EG1∪EG2; the graph G1∨G2 is called the join of G1 and G2, where VG1∨G2=VG1∪VG2 and EG1∨G2=EG1+G2∪xy:∀x∈VG1,∀y∈VG2. For example, Kn,m=On∨Om. The graph G¯=VG¯,EG¯ means the complement of G, where VG¯=VG and EG¯=xy:x,y∈VG,xy∉EG. The graph G^≔X,Y;E′, E′=xy:x∈X,y∈Y,xy∉E is called the quasicomplement of bipartite G=X,Y;E.In [1], Wiener introduced the Wiener index, WG=∑vi,vj∈VGdGvi,vj, for a connected graph G in 1947.We denoteDiG=∑vj∈VGdGvi,vj; then,(1)WG=12∑i=1nDiG.For a connected graphG, WWG=1/2∑vi,vj∈VGdGvi,vj+∑vi,vj∈VGdG2vi,vj is called its hyper-Wiener index, which is introduced by Klein et al. [2] in 1995.We denoteDDiG=∑vj∈VGdG2vi,vj; then,(2)WWG=14∑i=1nDiG+DDiG.In [3, 4], Plavšić et al. and Ivanciuc et al. gave the Harary index, HG=∑vi,vj∈VG1/dGvi,vj for a connected graph G, independently.We denoteD˜Gvi=∑vj∈VG1/dGvi,vj; then,(3)HG=12∑i=1nD˜Gvi.For a graphG, if it contains a path (cycle) containing all vertices of G, it is traceable (Hamiltonian); if there are paths containing all vertices of G between any two vertices in G, it is called to be Hamilton-connected; if there are paths containing all vertices of G from any vertex in G, it is called to be traceable from every vertex.Topological indices have attracted much attention in the literature, and they are widely applied in various fields of science and technology. Recently, some interesting results have been obtained, see [5–11]. Especially, some topological indices are used to characterize the Hamiltonian property of graphs. We refer readers to see [2, 12–21]. Among them, Hua and Ning [15] gave Hamiltonian conditions for a balanced bipartite graph with respect to the Wiener index and Harary index. Cai et al. [13], by the hyper-Wiener index, gave conditions for a balanced bipartite graph to be traceable and Hamiltonian and a t-connected graph to be Hamiltonian, respectively. Li [18, 19] gave Hamitonian conditions for a t-connected graph with respect to the Wiener index and Harary index, respectively. With the Wiener index, hyper-Wiener index, and Harary index, Yu et al. [20] gave conditions for a t-connected graph to be Hamilton-connected and then got conditions for it to be traceable from every vertex, as well as gave conditions for a nearly balance bipartite graph to be traceable. Especially, Liu et al. [16, 17] studied the Hamiltonian property of graphs with respect to the Wiener index and Harary index of complement of graph or quasicomplement of bipartite graph, respectively. As a continuance of these results, we also study the similar problems.In this paper, we discuss the hamiltonicity of graph by the Wiener index, hyper-Wiener index, and Harary index for quasicomplement or complement. In Section2, we present some notations and some lemmas needed in the following. In Sections 3 and 4, we present some conditions for a balanced bipartite graph G with δG≥t to be traceable and Hamiltion, respectively. In Section 5, we give sufficient conditions for a nearly balanced bipartite graph G with δG≥t to be traceable. In Sections 6 and 7, we present some conditions for a graph G with δG≥t to be traceable and Hamiltonian, respectively. In Sections 8 and 9, we provide some conditions for a t-connected graph to be Hamilton-connected and traceable from every vertex, respectively.


## 2. Preliminaries

Especially, in the following, for bipartite graphs, we always fix their partite sets. For instance,Os,t and Ot,s are seen as different bipartite graphs unless s=t.A graphG1⊔G2 is the graph obtained from G1∨G2 by deleting all possible edges between X1 and X2 and possible edges between Y1 and Y2, where GiXi,Yi,Ei,i=1,2 be bipartite graphs. Next, we denote some special classes of graphs:(4)Bnt=Ot,n−t⊔Kn−t,t1≤t≤n2,Cnt=Ot,n−t⊔Kn−t−1,t1≤t≤n2,Rnt=Kt,t+Kn−t,n−t1≤t≤n2,Qnt=Ot+1,n−t⊔Kn−t−1,t1≤t≤n2,Lnt=K1∨Kt+Kn−t−1,1≤t≤n−12,Nnt=Kt∨Kn−2t+tK1,1≤t≤n−12,L¯nt=Kt+1+Kn−t−1,1≤t≤n−12,N¯nt=Kt∨Kn−2t−1+t+1K1,1≤t≤n−12.Note thateCnt=nn−t−1+t2, and Cnt is not traceable.Lemma 1.
DenoteG^ as a quasicomplement of bipartite G with 2n vertices. If G^ is a connected balanced bipartite graph, then(5)WG^≤2n3−3n2+2n+2n−1eG.Proof.
AsG^ is a quasicomplement,(6)WG^=∑vi,vj∈VG^dG^vi,vj,=12∑j=12nDjG^,≤12∑j=12ndG^xj+2n−1n−dG^xj+2n2−4n+2,=4n3−5n2+2n+1−n∑j=12ndG^xj,=4n3−5n2+2n+1−n∑j=12nn−dGxj,=2n3−3n2+2n+n−1∑j=12ndGxj,=2n3−3n2+2n+2n−1eG.Lemma 2.
LetG^ be a quasicomplement of bipartite G with 2n vertices. If G^ is a connected balanced bipartite graph, then(7)WWG^≤2n4−5n3+5n2−n+2n2−n−1eG.Proof.
AsG^ is a quasicomplement,(8)WWG^=12∑vi,vj∈VG^dG^vi,vj+dG^2vi,vj,=14∑j=12nDjG^+DDjG^,≤14∑j=12ndG^xj+2n−1n−dG^xj+2n2−4n+2+14∑j=12ndG^xj+4n2−4n+1n−dG^xj+4n−13,=4n4−6n3+4n2−n−n2−0.5n−0.5∑j=12ndG^xj,=4n4−6n3+4n2−n−n2−0.5n−0.5∑j=12nn−dGxj,=2n4−5n3+5n2−n+2n2−n−1eG.Lemma 3.
LetG^ be a quasicomplement of bipartite G of order 2n. If G^ is a connected balanced bipartite graph, then(9)HG^≥4n3−n4n−2−2n−22n−1eG.Proof.
AsG^ is a quasicomplement,(10)HG^=∑vi,vj∈VG^1dG^vi,vj,=12∑j=12nD˜G^vj,≥12∑j=12ndG^xj+12n−1n−dG^xj+12,=n4n−122n−1+n−12n−1∑j=12ndG^xj,=n4n−122n−1+n−12n−1∑j=12nn−dGxj,=4n3−n4n−2−n−12n−1∑j=12ndGxj,=4n3−n4n−2−2n−22n−1eG.Lemma 4.
LetG¯ be a complement of G with n vertices. If G¯ is a connected graph, then(11)WG¯≤12nn−1+n−2eG.Proof.
(12)
W
G
¯
=
∑
v
i
,
v
j
∈
V
G
¯
d
G
¯
v
i
,
v
j
,
=
1
2
∑
j
=
1
n
D
j
G
¯
,
≤
1
2
∑
j
=
1
n
d
G
¯
x
j
+
n
−
1
n
−
1
−
d
G
¯
x
j
,
=
n
2
n
2
−
2
n
+
1
+
n
2
2
−
n
∑
j
=
1
n
d
G
¯
x
j
,
=
n
2
n
2
−
2
n
+
1
−
n
2
n
−
2
∑
j
=
1
n
n
−
1
−
d
G
x
j
,
=
n
2
n
−
1
+
n
−
2
2
∑
j
=
1
n
d
G
x
j
,
=
1
2
n
n
−
1
+
n
−
2
e
G
.Lemma 5.
LetG¯ be a complement of G with n vertices. If G¯ is a connected graph, then(13)WWG¯≤12nn−1+12n2−n−2eG.Proof.
(14)
W
W
G
¯
=
1
2
∑
v
i
,
v
j
∈
V
G
¯
d
G
¯
v
i
,
v
j
+
d
G
¯
2
v
i
,
v
j
,
=
1
4
∑
j
=
1
n
D
j
G
¯
+
D
D
j
G
¯
,
≤
1
4
∑
j
=
1
n
d
G
¯
x
j
+
n
−
1
n
−
1
−
d
G
¯
x
j
,
+
1
4
∑
j
=
1
n
d
G
¯
x
j
+
n
−
1
2
n
−
1
−
d
G
¯
x
j
=
n
2
4
n
2
−
2
n
+
1
+
2
+
n
−
n
2
4
∑
j
=
1
n
d
G
¯
x
j
,
=
n
2
4
n
2
−
2
n
+
1
+
2
+
n
−
n
2
4
∑
j
=
1
n
n
−
1
−
d
G
x
j
,
=
n
2
n
−
1
+
n
2
−
n
−
2
4
∑
j
=
1
n
d
G
x
j
,
=
1
2
n
n
−
1
+
1
2
n
2
−
n
−
2
e
G
.Lemma 6.
LetG¯ be a complement of G with n vertices. If G¯ is a connected graph, then(15)HG¯≥12n2−n−n−2n−1eG.Proof.
(16)
H
G
¯
=
∑
v
i
,
v
j
∈
V
G
¯
1
d
G
¯
v
i
,
v
j
,
=
1
2
∑
j
=
1
n
D
˜
G
¯
v
j
,
≥
1
2
∑
j
=
1
n
d
G
¯
x
j
+
1
n
−
1
n
−
1
−
d
G
¯
x
j
,
=
n
2
+
n
−
2
2
n
−
1
∑
j
=
1
n
d
G
¯
x
j
,
=
n
2
−
n
2
−
n
−
2
2
n
−
1
∑
j
=
1
n
d
G
x
j
,
=
1
2
n
2
−
n
−
n
−
2
n
−
1
e
G
.


## 3. Traceable of Balanced Bipartite Graphs

Lemma 7 (see [22]).
LetG be a balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(17)eG>n2−nt−2n+t2+4t+4,for some integer t, then G is traceable or G⊆Qnt or t=1, G⊆Rn1.Theorem 1.
LetG^ be a connected balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(18)WG^>4n3−2t+9n2+2t2+10t+14n−2t+22,for some integer t, then G is traceable or t=1 and G⊆Rn1.Proof.
SinceWG^>4n3−2t+9n2+2t2+10t+14n−2t+22, by Lemma 1, we get eG>n2−nt−2n+t2+4t+4. By Lemma 7, we obtain that G is traceable or G⊆Qnt or t=1, G⊆Rn1.
IfG⊆Qnt: because G^ is connected and δG≥t≥1, we get eG≤n2−nt−n+t2+t−n−t−1−t<n2−nt−2n+t2+4t+4. It is in contradiction with the above.
Ift=1: because G^ is connected, G⊆Rn1.Theorem 2.
LetG^ be a connected balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(19)WWG^>4n4−2t+10n3+2t2+9t+14n2−t2+3t+3n−t+22,for some integer t, then G is traceable or t=1, G⊆Rn1.Proof.
SinceWWG^>4n4−2t+10n3+2t2+9t+14n2−t2+3t+3n−t+22, by Lemma 2, eG>n2−nt−2n+t2+4t+4. By Lemma 7, G is traceable or G⊆Qnt or t=1, G⊆Rn1. By the same discussion as the proof of Theorem 1, the conclusion is established.Theorem 3.
LetG be a connected balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(20)HG^<4t+12n2−4t2+20t−25n+4t2+16t+164n−2,for some integer t, then G is traceable or t=1, G⊆Rn1.Proof.
SinceHG^<4t+12n2−4t2+20t−25n+4t2+16t+16/4n−2, by Lemma 3, we get eG>n2−nt−2n+t2+4t+4. By Lemma 7, we obtain that G is traceable or G⊆Qnt or t=1, G⊆Rn1. By the same discussion as the proof of Theorem 1, the conclusion is established.


## 4. Hamiltonian of Balanced Bipartite Graphs

Lemma 8 (see [23]).
LetG be a balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(21)eG>n2−nt−n+t2+2t+1,for some integer t, then G is Hamiltonian or G⊆Bnt.Theorem 4.
LetG^ be a connected balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(22)WG^>4n3−2t+7n2+2t+2t+12+4n−2t+12,for some integer t, then G is Hamiltonian.Proof.
SinceWG^>4n3−2t+7n2+2t+2t+12+4n−2t+12, by Lemma 1, we get eG>n2−nt−n+t2+2t+1. By Lemma 8, G is Hamiltonian or G⊆Bnt.
IfG⊆Bnt: because G^ is connected and δG≥t≥1, we get eG≤n−t2+nt−n−t−t<n2−nt−n+t2+2t+1. It is in contradiction with the above.Theorem 5.
LetG^ be a connected balanced bipartite graph with 2n vertices. If δG≥t≥1, n≥2t+3, and(23)WWG^>4n4−2t+8n3+2t2+5t+7n2−t2+t+1n−t+12,for some integer t, then G is Hamiltonian.Proof.
SinceWWG^>4n4−2t+8n3+2t2+5t+7n2−t2+t+1n−t+12, by Lemma 2, we get eG>n2−nt−n+t2+2t+1. By Lemma 8, G is Hamiltonian or G⊆Bnt. By the same discussion as the proof of Theorem 4, the conclusion is established.Theorem 6.
LetG^ be a connected balanced bipartite graph of with 2n vertices. If δG≥t≥1, n≥2t+3, and(24)HG^<4t+8n2−4t2+12t+9n+4t2+8t+44n−2,for some integer t, then G is Hamiltonian.Proof.
SinceHG^<4t+8n2−4t2+12t+9n+4t2+8t+4/4n−2, by Lemma 3, eG>n2−nt−n+t2+2t+1. By Lemma 8, G is Hamiltonian or G⊆Bnt. By the same discussion as the proof of Theorem 4, the conclusion is established.


## 5. Traceable of Nearly Balanced Bipartite Graphs

Lemma 9 (Yu, Fang, and Fan [24]).
LetG be a nearly balanced bipartite graph with 2n−1 vertices. If δG≥t≥1, n≥2t+1, and(25)eG>n2−nt−2n+t2+2t+1,for some integer t, then G is traceable or G⊆Cnt.Theorem 7.
LetG^ be a connected nearly balanced bipartite graph with 2n−1 vertices. If n≥2t+1, δG≥t≥1, and(26)WG^>4n3−2t+14n2+4t+2t+12+16n−4t+12−4,for some integer t, then G is traceable.Proof.
LetG=GX,Y;E, where X=x1,x2,…,xn and Y=y1,y2,…,yn−1, then(27)WG^=∑vi,vj∈VG^dG^vi,vj=12∑j=12n−1DjG^≤12∑j=1ndG^xj+2n−3n−1−dG^xj+2n2−2n+1+12∑j=1n−1dG^yj+2n−3n−dG^yj+2n2−4n+4=4n3−12n2+12n−4−n−2∑j=1ndG^xj+∑j=1n−1dG^yj=2n3−6n2+8n−4+n−2∑j=1ndGxj+∑j=1n−1dGyj=2n3−6n2+8n−4+2n−2eG,where dG^xj=n−1−dGxj and dG^yj=n−dGyj. Because WG^>4n3−2t+14n2+4t+2t+12+16n−4t+12−4, we get eG>n2−nt−2n+t2+2t+1. By Lemma 9, we get G is traceable or G⊆Cnt.
IfG⊆Cnt: because G^ is connected and δG≥t≥1, we get eG≤t2+nn−t−1−n−t−1−t<n2−nt−2n+t2+2t+1. It is in contradiction with the above.Theorem 8.
LetG^ be a connected nearly balanced bipartite graph with 2n−1 vertices. If n≥2t+1, δG≥t≥1, and(28)WWG^>4n4−2t+18n3+2t2+9t+652n2−5t2+12t+532n+2t2+4t+8,for some integer t, then G is traceable.Proof.
LetG=GX,Y:E, where X=x1,x2,…,xn and Y=y1,y2,…,yn−1, then(29)WWG^=12∑vi,vj∈VG^dG^vi,vj+dG^2vi,vj=14∑j=12n−1DjG^+DDjG^≤14∑j=1ndG^xj+2n−3n−1−dG^xj+2n2−2n+1+14∑j=1ndG^xj+2n−32n−1−dG^xj+4n−12n−1+14∑j=1n−1dG^yj+2n−3n−dG^yj+2n−4n−2+14∑j=1n−1dG^yj+2n−32n−dG^yj+2n−42n−2=4n4−16n3+512n2−392n+6+14−4n2+10n−4∑j=1ndG^xj+∑j=1n−1dG^yj=2n4−9n3+372n2−352n+6+144n2−10n+4∑j=1ndGxj+∑j=1n−1dGyj=2n4−9n3+372n2−352n+6+2n2−5n+2eG,where dG^xj=n−1−dGxj and dG^yj=n−dGyj. Because WWG^>4n4−2t+18n3+2t2+9t+65/2n2−5t2+12t+53/2n+2t2+4t+8, we get eG>n2−nt−2n+t2+2t+1. By Lemma 9, we obtain that G is traceable or G⊆Cnt. By the same discussion as the proof of Theorem 7, the conclusion is established.Theorem 9.
LetG^ be a connected nearly balanced bipartite graph with 2n−1 vertices. If n≥2t+1, δG≥t≥1, and(30)HG^≤4t+8n2−4t2+16t+17n+8t2+16t+84n−6,for some integer t, then G is traceable or G⊆Cntt≤6.Proof.
LetG=GX,Y:E, where X=x1,x2,…,xn and Y=y1,y2,…,yn−1, then(31)HG^=∑vi,vj∈VG1dG^vi,vj=12∑j=1nD˜G^vj≥12∑j=1ndG^xj+12n−3n−1−dG^xj+12+12∑j=1n−1dG^yj+12n−3n−dG^yj+12=4n2−5n4n−6+n−22n−3∑j=1ndG^xj+∑j=1n−1dG^yj=4n3−8n2+3n4n−6−n−22n−3∑j=1ndGxj+∑j=1n−1dGyj=4n3−8n2+3n4n−6−2n−22n−3eG,where dG^xj=n−1−dGxj and dG^yj=n−dGyj. Because(32)HG^≤4t+8n2−4t2+16t+17n+8t2+16t+84n−6,we get eG>n2−nt−2n+t2+2t+1. By Lemma 9, we obtain that G is traceable or G⊆Cnt. Note that t≥7 and HCnt^=1/4n2+2tn−n−2t2 > 4t+8n3−4t2+24t+33n2+16t2+48t+44n−16t2−32t−19/4n2−14n+12. If G⊆Cnt, then HG^>HCnt^. The conclusion is established.


## 6. Traceable of Graphs

Lemma 10 (see [23]).
LetG be a graph with n≥6t+10 vertices, where t is an integer. If δG≥t and eG>n−t−22+t2+3t+2, then G is traceable unless G⊆L¯nt or N¯nt.Theorem 10.
LetG¯ be a connected graph with n≥6t+10 vertices, where t is an integer. If δG≥t and(33)WG¯>12n3−2t+6n2+3t2+15t+19n−6t2−22t−20,then G is traceable.Proof.
SinceWG¯>1/2n3−2t+6n2+3t2+15t+19n−6t2−22t−20, by Lemma 4, we get eG>n−t−22+t2+3t+2. By Lemma 10, we obtain that G is traceable unless G⊆L¯nt or N¯nt.
IfG⊆L¯nt: note that WL¯nt¯=n2−2n−tn+t2+2t+1. Then, if G⊆L¯nt, we have WG¯≤WL¯nt<1/2n3−2t+6n2+3t2+15t+19n−6t2−22t−20, a contradiction.
IfG⊆N¯nt: note that WN¯nt¯=1/22n2−4n−6tn+5t2+7t+2. Then, if G⊆N¯nt, we have WG¯≤WN¯nt¯<1/2n3−2t+6n2+3t2+15t+19n−6t2−22t−20, a contradiction.Theorem 11.
LetG¯ be a connected graph with n≥6t+10 vertices, where t is an integer. If δG≥t and(34)WWG¯>14n4−12t+32n3+34t2+134t+154n2−34t2+74t+12n−32t2−112t−5,then G is traceable.Proof.
SinceWWG¯>1/4n4 − 1/2t+3/2n3 + 3/4t2+13/4t+15/4n2 − 3/4t2+7/4t+1/2n − 3/2t2−11/2t−5, by Lemma 5, we get eG>n−t−22+t2+3t+2. By Lemma 10, we obtain that G is traceable or G⊆L¯nt or N¯nt.
IfG⊆L¯nt: note that WWL¯nt¯=1/23n2−7n−4tn+4t2+8t+4. Then, if G⊆L¯nt, we have WWG¯≤WWL¯nt¯<1/4n4 − 1/2t+3/2n3 + 3/4t2+13/4t+15/4n2 − 3/4t2+7/4t+1/2n − 3/2t2−11/2t−5, a contradiction.
IfG⊆N¯nt: note that WWN¯nt¯=3n2−7n−10tn+9t2+13t+4. Then, if G⊆N¯nt, we have WWG¯≤WWN¯nt¯<1/4n4 − 1/2t+3/2n3 + 3/4t2+13/4t+15/4n2 − 3/4t2+7/4t+1/2n − 3/2t2−11/2t−5, a contradiction.Theorem 12.
LetG¯ be a connected graph with n≥6t+10 vertices, where t is an integer. If δG≥t and(35)HG¯<2t+4n2−3t2+15t+18n+6t2+22t+202n−2,then G is traceable.Proof.
SinceHG¯<2t+4n2−3t2+15t+18n+6t2+22t+20/2n−2, by Lemma 6, we get eG>n−t−22+t2+3t+2. By Lemma 10, we obtain that G is traceable unless G⊆L¯nt or N¯nt.
IfG⊆L¯nt: note that HL¯nt¯=1/4n2+n+2tn−2t2−2. Then, if G⊆L¯nt, we have HG¯≥HL¯nt¯>2t+4n2−3t2+15t+18n+6t2+22t+20/2n−2, a contradiction.
IfG⊆N¯nt: note that HN¯nt¯=1/4n2+n+2tn−2t2−6t−2. Then, if G⊆N¯nt, we have HG¯≥HN¯nt¯>2t+4n2−3t2+15t+18n+6t2+22t+20/2n−2, a contradiction.


## 7. Hamiltonian of Graphs

Lemma 11. (see [23]).
LetG be a graph with n≥6t+5 vertices, where t is an integer. If δG≥t and(36)eG>n−t−12+t2+2t+1,then G is Hamiltonian or G⊆Lnt or Nnt.Theorem 13.
LetG¯ be a connected graph with n≥6t+5 vertices, where t is an integer. If δG≥t and(37)WG¯>12n3−2t+4n2+3t2+11t+19n−6t2−14t−8,then G is Hamiltonian.Proof.
SinceWG¯>1/2n3−2t+4n2+3t2+11t+19n−6t2−14t−8, by Lemma 4, we get eG>n−t−12+t2+2t+1. By Lemma 11, we obtain that G is Hamiltonian or G⊆Lnt or Nnt.
IfG⊆Lnt: note that WLnt¯=n2−tn−3n+t2+t+2. Then, if G⊆Lnt, we have WG¯≤WLnt¯<1/2n3−2t+4n2+3t2+11t+19n−6t2−14t−8, a contradiction.
IfG⊆Nnt: note that WNnt¯=n2−3tn−n+5/2t2+3/2t. Then, if G⊆Nnt, we have WG¯≤WNnt¯<1/2n3−2t+4n2+3t2+11t+19n−6t2−14t−8, a contradiction.Theorem 14.
LetδG≥t and G¯ be a connected graph with n≥6t+5 vertices for some integers t satisfying the following condition:(38)WWG¯>14n4−12t+1n3+34t2+94t+32n2−34t2+34t+14n−32t2+72t+2.
Therefore,G is Hamiltonian.Proof.
SinceWWG¯>1/4n4 − 1/2t+1n3 + 3/4t2+9/4t+3/2n2 − 3/4t2+3/4t+1/4n − 3/2t2+7/2t+2, by Lemma 5, we get eG>n−t−12+t2+2t+1. By Lemma 11, we obtain that G is Hamiltonian or G⊆Lnt or Nnt.
IfG⊆Lnt: note that WWLnt¯=3n2−4tn−9n+4t2+4t+6. Then, if G⊆Lnt, we have WWG¯≤WWLnt¯<1/4n4 − 1/2t+1n3 + 3/4t2+9/4t+3/2n2 − 3/4t2+3/4t+1/4n − 3/2t2+7/2t+2, a contradiction.
IfG⊆Nnt: note that WWNnt¯=3n2−10tn−3n+9t2+5t. Then, if G⊆Nnt, we have WWG¯≤WWNnt¯<1/4n4 − 1/2t+1n3 + 3/4t2+9/4t+3/2n2 − 3/4t2+3/4t+1/4n − 3/2t2+7/2t+2, a contradiction.Theorem 15.
LetG¯ be a connected graph with n≥6t+5 vertices for some integer t. If δG≥t and HG¯<2t+2n2−3t2+11t+8n+6t2+14t+8/2n−2, then G is Hamiltonian.Proof.
SinceHG¯≤2t+2n2−3t2+11t+8n+6t2+14t+8/2n−2, by Lemma 6, we get eG>n−t−12+t2+2t+1. By Lemma 11, we obtain that G is Hamiltonian unless G⊆Lnt or Nnt.
IfG⊆Lnt: note that HLnt¯=1/4n2−3n+2tn−2t2−2t+2. Then, if G⊆Lnt, we have HG¯≥HLnt¯ > 2t+2n2−3t2+11t+8n+6t2+14t+8/2n−2, a contradiction.
IfG⊆Nnt: note that HNnt¯=1/4n2−n−3t2+t. Then, if G⊆Nnt, we have HG¯≥HNnt¯ > 2t+2n2−3t2+11t+8n+6t2+14t+8/2n−2, a contradiction.


## 8. Hamilton-Connected of Graphs

Lemma 12 (see [20]).
LetG be a t-connected graph with n vertices, where t≥2. If eG>nn−1−tn−t−1/2, then G is Hamilton-connected.
By Lemmas 4, 5, 6, and 12 and by direct computations, we get Theorems 16, 17, and 18, respectively.Theorem 16.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If (39)WG¯>12n3−12t+2n2+12t2+3t+1n−t2−t,then G is Hamilton-connected.Theorem 17.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If(40)WWG¯>14n4−14t+2n3+14t2+2t+1n2−14t2−tn−12t2−12t,then G is Hamilton-connected.Theorem 18.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If(41)HG¯<t+1n2−t2+3t+1n+2t2+2t2n−1,then G is Hamilton-connected.


## 9. Traceable from Every Vertex of Graphs

Lemma 13 (see [20]).
LetG be a t-connected graph with n vertices, where t≥2. If eG>nn−1−tn−t/2, then G is traceable from every vertex.
By Lemmas 4, 5, 6, and 13 and by direct computation, we get Theorems 19, 20, and 21, respectively.Theorem 19.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If(42)WG¯>12n3−12t+1n2+12t2+2t+1n−t2,then G is traceable from every vertex.Theorem 20.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If(43)WWG¯>14n4−14t+2n3+14t2+t+1n2−14t2−2tn−12t2,then G is traceable from every vertex.Theorem 21.
LetG be a t-connected graph with n vertices and G¯ be a connected graph, where t≥2. If(44)HG¯<t+1n2+−t2−2t−1n+2t22n−2,then G is traceable from every vertex.



---

*Source: 2047406-2019-11-15.xml*