**On
k-path Hamiltonian graphs, neighborhood union conditions and degree sum
conditions involving distance two**

Department of Mathematics, Qiongzhou University, Wuzhishan, Hainan, 572200, P.R.China

**Abstract:**** **In 1969, Kronk investigated the k-path Hamiltonian using nonadjacent
vertices. In this present paper, we investigate the k-path Hamiltonian path
using nonadjacent vertices involving distance.

（注：我们改进的这个K-path hamiltonian graphs结果主要由指导**许多博士门徒成了计算机大师（如既有“现代计算机之父”，又有“计算机之母”**的耶鲁大学**Ore院士评审决定**。

关于k-path Hamiltonian graphs领域，虽然较受很多专家关注，但对进一步的发展较困难，使得迄今只完成无向和有向图的**“****不相邻****”**课题以及无向最大平面图以及和线图的关系，并定理1的**“****不相邻****”**的证明仅需几行字，但从下面定理2和定理3看到** “****距离是****2”**的**“****距离是****2****”**的情况**“**1≤|*N*(*x*)∩*N*(*y*)|≤α**”****“****不相邻****”**是非常容易判断的，但**“****距离是****2****”****“**1≤|*N*(*x*)∩*N*(*y*)|≤α-1**”**更是几乎不可能判别很多点对）。最下面的定理5可能更出乎世界各国每一个图论专家的意料！ ）

In 1969, **Kronk
proved the following Theorem 1 [1] on k-Hamiltonian graphs.**

**课题一**、

**Theorem 1**(Kronk [1]). If *G* is a connected graph with *n* vertices and *d*(*u*)+*d*(*v*)≥*n*+k for each pair of distinct nonadjacent vertices *u*,*v
*in *G*, then *G* is k-path Hamiltonian.

(定理1 (Kronk [1]).若*n*阶图*G*的不相邻的任意两点*x*,*y*均有*d*(*x*)+*d*(*y*)≥*n*+k，则*G*是k-path哈密顿图）

In this present paper, we generalize k-path Hamiltonian path involving distance as follows.

**Theorem 2**(Kewen Zhao). If *G* is a
2-connected graph with *n* vertices and
*d*(*u*)+*d*(*v*)≥*n*-1+k for each pair of distinct
non-adjacent vertices *u*,*v *of*
d(u,v)*=* *in*G*,
then *G* is k-path Hamiltonian path.

(定理2. 若*n*阶图*G*的距离为2的任意两点*x*,*y*均有*d*(*x*)+*d*(*y*)≥*n*+k，则*G*是k-path哈密顿路）

To prove **Theorem
2**, we need the following four lemmas of Erdös [4], Paul Erdös,Tibor Gallai[6]（Gallai的导师Kőnig的导师闵可夫斯基是爱因斯坦的老师并对其相对论的发展又很大影响，Gallai的博士László
Lovász,是获得3次国际数学奥林匹克竟赛金奖的国际数学联盟主席）, Zhao, **Lai**, Shao
[11]**.**

**Lemma
1**(Zhao-Lai-Shao [11]). If *G* is a connected graph with *n* vertices and *d*(*u*)+*d*(*v*)≥*n*-1 for each pair of distinct non-adjacent vertices *u*,*v
*of* d(u,v)*=* *in*G*, then *G* has Hamiltonian
path.

**Lemma
2**(Zhao-Lai-Shao [11]). If *G* is a 2-connected graph with *n* vertices and *d*(*u*)+*d*(*v*)≥*n* for each pair of distinct non-adjacent vertices *u*,*v
*of* d(u,v)*=* *in*G*, then *G* is Hamiltonian.

**Lemma
3.** (Paul Erdös [4].) G has a Hamiltonian circuit
if every vertex of G has valency at least k, where either k ³n/2, or k<n/2 and G
has at least f(n, k) edges, where f(n, k)=max {(^{n}^{-}^{k}_{2})+k^{2}+1, (^{[(n+2)/2]}_{2})
+[(n-1)/2]^{2}+1}, (This bound on the number of
edges is the least possible, again in

**Lemma
4. **(Paul Erdös, Tibor Gallai([6], Theorem
(2.7)).) Let G be aundirected graph on n vertices with at least d{n- 1)/2 + 1
edges, where d > 1.Then G contains a circuit of length at least d+l

**The Proof of Theorem 2. **

By *d*(*u*)+*d*(*v*)≥*n*-1+k
for each pair of distinct non-adjacent vertices *u*,*v *of* d(u,v)*=2, and *d*(*u*) ≤n-|{u,v}|=n-2 for
each pair of distinct non-adjacent vertices *u*,*v *of*
d(u,v)*=2, we have *d*(*v*) ≥*n*-1+k-d(u)≥k+1
for each vertex *v* in G.

Let *P _{k}*=

**Claim 1.** G-*P _{k}*\{

**Claim 2. **G-*P _{k}* has at
most two components and if G-

**Proof of Claim 1.** If H, and T be two components of G-*P _{k}*\{

**Proof of Claim 2.** If H, T and Q be three components of G-*P _{k}*. (i). If there exists a vertex of

Now, we consider the following cases.

**Case 1.** G-*P _{k}* has two
components H, T.

By *d*(*u*)+*d*(*v*)≥*n*-1+k
for each pair of distinct non-adjacent vertices *u*,*v *of* d(u,v)*=* *in*H*, we have *d _{H}*(

Next, by *d*(*u*)+*d*(*v*)≥*n*-1+k for each pair of distinct non-adjacent vertices *u*,*v
*of* d(u,v)*=* *in*G*, we can check that* d _{G}*

**Case 2. **G-*P _{k}* is connected..

** **We consider the following two
subcases.

**Subcase 2.1. **G-*P _{k}* has a Hamiltonian path.

Let P=*y*_{1}*y*_{2}¼*y _{n-k-1}*

If i=j-1, clearly, the proof is complete.

If i≤j-2. We consider

By *d*(*y*_{i-1})+*d*(*x _{0}*)≥

(1). If *d _{G}*

In this
case, we have the following. (i). When *y*_{t}ÎN* _{P}*(

(2). If *d _{G}*

In this case, if *x*_{0}
or *x _{k}* is adjacent to

**Subcase 2.2. **G-*P _{k}* has not any Hamiltonian
path.

** **In this case,** **by *d*(*u*)+*d*(*v*)≥*n*-1+k
for each pair of distinct non-adjacent vertices *u*,*v *of* d(u,v)*=* *in*G*, we can check that* d _{H}*(

Therefore, The
proof is complete.

我感到上面证明中我用到的多数方法都非常漂亮，很多方法就象华山一条路。当你纵向前进不行退而横向探究，这样周而复始多次都不行后，忽然发现华山一条路，那是何其妙之事！而且当再回过头来多次看，似乎永远都找不到其它出路时，那真是奇哉壮哉…

**Theorem 3 ****(****Kapoor, Theckedath****, 1971****)**. If *G* is a connected graph with *n* vertices and *d*(*u*)+*d*(*v*)≥*n*-1+k for each pair of distinct non-adjacent vertices *u*,*v
*in *G*, then *G* is k-path Hamiltonian path.

(定理3. 若*n*阶图*G*的不相邻的任意两点*x*,*y*均有*d*(*x*)+*d*(*y*)≥*n*-1+k，则*G*是k-path哈密顿路-此定理见[3]）

**Proof. **Let *P _{k}*=

A digraph D of order p is of
Ore-type (k) if od(u) + id(u) ≥p + k whenever
u and v are distinct vertices for which uv is not an arc of D.. And a digraph D
of order p is of Ore-type2 (k) if od(u) + id(u) ≥p
+ k whenever u and v are distinct vertices for which d(u,v)=2 .

John Roberts ontained the
following result in [3].

Theorem 4. If a nontrivial digraph D is of Ore-type
(k), k > 0, then D is k-path hamiltonian.

We conjecture that

**Conjecture**. If a nontrivial digraph D is of Ore-type2
(k), k > 0, then D is k-path hamiltonian.

（对哈密顿图有时几行字都很不容易，象这里的张校长的几行字都要求得到**管**和**田**这两个中国**最利害**的大师提供的帮助和意见等，这里的几行字更是照耀中国**光耀世界**）

**References**

1、 Hudson** Kronk,** A note on k-path Hamiltonian
graphs. *J. Combinatorial Theory* **7
**1969*,* 104–106.

2、 Kenneth Reid**, **Carsten Thomassen,
Edge sets contained in circuits. *Israel** J. Math.* **24
**(1976), no. 3–4, 305--319.

3.、John Roberts, A
sufficient condition for k-path Hamiltonian digraphs. *Bull.
Amer. Math. Soc.** ***82
***(1976), no. 1, 63--65.*

4、Paul Erdös， 'Remarks on a paper of P6sa', Magyar Tud. Akad. Mat. Kutatd
Int.Kozl. 7 (1962) 227-229.

5、Paul Erdös，'Unsolved
problems in graph theory and combinatorial analysis', inCombinatorial
mathematics and its applications (Proc. I.M.A. Conference,Oxford, July 1969),
ed. D. J. A. Welsh (Academic Press, London, 1971),97-109.

6、Paul Erdös，Tibor Gallai，On
maximal paths and circuits of graphs', Acta Math.Acad. Sci. Hungar. 10 (1959)
337-359.

7、Günter Schaar, On k-path traceable graphs. *Journal of
Information Processing and Cybernetics ***24 **(1988),
no. 1-2, 19--30.（此杂志现名*Journal
of Automata, Languages and Combinatorics*-即《自动机、语言与组合学杂志》--主编是1972年获博士学位、1987年任计算机领域曾多次排名德国第一的马格德堡大学计算机系教授的世界大师Jürgen Dassow）

8、D. R. Woodall, Sufficient conditions
for circuits in graphs, Proc.
London Math. Soc. (3) 24 (1972),
739-755.

9、Ilker Baybars,
On k-path Hamiltonian
maximal planar graphs. Discrete Math.
40 (1982), no. 1, 119--121.

10、Crispin Nash-Williams,
'On Hamiltonian circuits in finite graphs', Proc-Amer. Math. Soc. 17 (1966) 466

11、 Kewen Zhao, Hongjian Lai, Yehong Shao,** **New
sufficient condition for Hamiltonian graphs. *Appl. Math. Lett.* **20
**(2007), no. 1, 116--122.

12、德国多特蒙德工业大学终身教授、罗马尼亚科学院院士**Tudor Zamfirescu**

13、**Tudor Zamfirescu**院士

**14****、****Richard**** Denman, **

**15****、**Kewen
Zhao, Hongjian Lai, **Ju**** ****Zhou, **Hamiltonian-connected graphs. *Comput. Math. Appl.* **55**** **(2008), no. 12, 2707--2714.

值得关注Häggkvist和Thomassen的论文Circuits
through specified edges证明：“k≥a+t则任何总长不超过t的不交路都含在一哈密顿圈中”和“t+1连通图的任一t独立边都含在一圈中”

开创k-path哈密顿图的Hudson
Kronk的导师是John Hocking，他的导师又是美国数学协会主席Gail
Young，此主席的导师是海南琼州大学师爷叔Robert Moore。

**附注**：上面意要把 k-path
Hamiltonian推广到k-path
traceable的第7篇作者Günter
Schaar教授1962年毕业后一直在这1765年创办的弗莱贝格工业大学工作，不过，前面的意义更大发展都仍困难。他有几个博士其中1983年获得博士的Hanns-Martin
Teichert教授和1985年获得博士的Martin Sonntag教授还算发表了约20篇论文，其他博士都几乎没有论文，见Teichert的博士提目“*Hamiltonsche*…”和Sonntag的博士提目“*Hamiltonsche*…”都是做哈密顿图（他们三人的论文都几乎全做哈密顿图，也都仅是**二、三十篇**，这是因哈密顿图之难吗。可见Schaar教授的主页和**论文**，Teichert教授的**论文**和Sonntag教授的网页和**论文**；更早的2个博士Goebel
Rotraud的博士题目是“…Hamiltoneigenschaften”和Roland
Schmieder在“数学评论”没有看到论文，Peter Heinrich有6篇并3篇是和导师Günter Schaar合作的哈密顿图论文）。这大学是**世界上最古老的技术大学**，确实，技术似乎是在这大学创办之后的18、19世纪才大发展，这大学欢迎我国211大学毕业的硕士生去读博士生。象这三人中二人现在该大学，此外，著名哈密顿图权威、《图论与组合》执行编委Schiermeyer教授90年代在亚琛工业大学培

下面**定理****5**更是出乎世界各国每一个图论专家的意料**！**我想每一个图论专家在20多年前创立此条件的哈密顿图结果起这二十多年来必定会认为+k条件的图G全部都是k-path哈密顿图--这是有道理的，因为据图论“教父Bondy”的Meta猜想特别是象上面等以前已完成的所有条件都全是k-path哈密顿图，就是我不做这问题之前我也很肯定坚信“全部图G都是k-path哈密顿图”。然而，从我下面证明看到不只存在一个非k-path哈密顿图，而且还是有好几类！** **

**课题二**、

定理5(Kewen
Zhao)：若*n*阶2连通图*G*的距离为2的任意两点*x*,*y*均有|*N*(*x*)∪*N*(*y*)|≥*n*-δ+k，则*G*是k-path哈密顿图或几类非k-path哈密顿图。

To prove **Theorem
5**, we need the following two lemmas by Zhao
[15]**.**

**引理****1 **(Zhao
[15]). 若*n*阶2连通图*G*的距离为2的任意两点*x*,*y*均有|*N*(*x*)∪*N*(*y*)|≥*n*-δ，则*G*是哈密顿图。

**Lemme 2.** If the connectivity of graph *G* of order *n*≥3 is 1, and if |N(*x*)∪N(*y*)|≥*n*-d-2
for each pair of nonadjacent vertices *x*,*y* of*
d(u,v)*=* *in*G*,
then *G* is **(K _{h}**#

Where K_{h} and K_{n-h-1} are two disjoint
complete graphs of orders h and n-h-1, respectively, and u=V(**K _{1}**) is a cut vertex of G,
and the vertex set of G to be V(

**Proof.** Let u be a cut vertex of G. We claim that
G-u has only just two components denoted by H, T and they are two complete
subgraphs. Otherwise, if H is not complete subgraph, let x,yÎV(H) with d(x,y)=2, and w is any a vertex
of T, then we can check that |N(*x*)∪N(*y*)|≤|V(*G*)|-|{x,y}|-|V(T)|
≤n-2-(d+1) ≤n-3- d, a contradiction. Thus, H is complete
subgraph. Similarly, we can prove that each component of G-u is complete
subgraph. Furthermore, if G-u has three components H, T and Q, then, let x,y be
two vertices that are adjacent to cut vertex u and belong to H, T,
respectively. Then similarly, we can check that |N(*x*)∪N(*y*)|≤|V(*G*)|-|{x,y}|-|V(Q)| ≤n-2-(d+1) ≤n-3- d, a contradiction.

**The proof of Theorem 5. **

let *P**=*x*_{0}*x*_{1}¼*x _{k}*

Claim
that if H=G-P* is not connected, then H has at most two components and each
component of H is complete subgraph.

Otherwise,
if Q and T are two components of G-*P**
with that T is not complete. So, without loss of generality, assume x, y are
two vertices of T with d(x,y)=2, then we can check that |N_{H}(*x*)∪N_{H}(*y*)|≤|V(*T*)|-|{x,y}|≤|V(G-P*)|-|V(Q)|-|{x,y}|≤|V(H)|-d(H)-2,
which contradicts inequality (*). So each component of H is complete. If H has
at least three components Q, T, R. (i). If there exist vertex x in Q and y in T
with d(x,y)=2, we can check that |N_{H}(*x*)∪N_{H}(*y*)|≤|V(Q)|+|V(T)|-|{x,y}|≤|V(H)|-|V(R)|-|{x,y}|≤|V(H)|-d(H)-**2**, which contradicts the above
inequality (*).

(ii).
If there do not exist two vertices of that their distance is 2. Without loss of
generality, we may assume that *x _{j}*

Thus,
Claim holds.

Then
we consider the following three cases.

**Case
1.**
H is 2-connected.

let *P**=*x*_{0}*x*_{1}¼*x _{k}*

In
this case, by Lemma 3, H has Hamiltonian path.

**Subcase
1.1.**
If H has Hamiltonian cycle.

By |N(*x*)∪N(*y*)|≥n-d+k
for any two vertices x,y in G with d(x,y)=2 and |N(*x*)∪N(*y*)|≤n-|{x,y}|=n-2, so d≥k+2. Thus, each of {*x*_{0},*x _{k}*

**Subcase
1.2.**
If H has not any Hamiltonian cycle.

In this case, we consider T=G-(*P**\{*x*_{o}}).

By |N(*x*)∪N(*y*)|≥n-d+k for any two
vertices x,y in G with d(x,y)=2 and d£d(T)+|V(T)|,
we have |N_{T}(*x*)∪N_{T}(*y*)|≥n-d+k-|V(*P**\{*x*_{o}})|=(|V(T)|+|V(P*)|)-(d(T)+|V(*P**\{*x*_{o}})|)+k-|V(*P**\{*x*_{o}})|=|V(T)|-d(T)
for any two vertices x,y in T with d_{G}(x,y)=2, where T=G-(*P**\{*x*_{o}})_{.}

Since
H=G-P* is 2-connected, and *x*_{o}
is adjacent to at least two vertices of H, so T=G-(*P**\{*x*_{o}}) is
also 2-connected. By Lemma 3, T has Hamiltonian cycle, so we can complete the
proof by the similar arguments as Subcase 1.1.

**Case
2.**
the connectivity of H is 1.

** **In this case, by
Lemma 4, *H=***K _{h}**#

(i).
If *x*_{0},*x _{k}*

(ii).
If *x*_{0},*x _{k}*

Otherwise, if v of K_{h}
is not adjacent to *x*_{0}, then
we can check that |N_{H}(*v*)∪N_{H}(*x*_{o})|≤|V(H)|-|{v}|-|V(K_{(n-k-1)-h-1}}|≤|V(H)|-d(H)-2,, which contradicts inequality (*).

Similarly, if some vertex *x _{i}* of P*\{

In this case, G is not k-path
Hamiltonian and we denote graph G by **(****K _{h}**#

**Case
3. **H
is not connected.

In this
case, by the similar arguments to the Proof of Lemma 2, each component of G-P*
must be complete subgraph. Then, we have the following claim.

Claim.
G-P* has at most two component.

Otherwise, if G-P* has at least three
components Q, R and T. We consider the following.

(i). If two of (Q, R, T) have common vertex
in P*.

Without loss of generality, assume *x _{i}_{
}*of P* is adjacent to vertex x in Q
and y in R. Then similarly, we can check that | N

(ii). If any two of (Q, R, T) has not any common vertex in
P*.

In this case, there must exist *x _{i}_{
}*of P* is adjacent to vertex x in Q
and

Thus, Chaim holds. In this case, G has not any Hamiltonian
cycle containing path *P**, and we
denote G by G=(T∪Q)#G[P*], where T, Q are
two complete subgraphs.

Therefore,
the proof is complete.

**新课题**、

图的线图的k-path哈密顿图的条件.

开创的无爪图的度和条件以及邻域并条件的工作.

开创的偶图的度和条件以及邻域并条件的工作.