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

Kewen Zhao

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”的证明却要用几页并还需更多引理（如此在美国MR Lookup即”数学评论查询”见仍还没有见到发表我们下面证明的“距离是2”的情况）。而若再用限制“1≤|N(x)∩N(y)|≤α-1”不仅非常艰难更是几乎不可能解决（这是由k-path构造特性决定的：因“不相邻”是非常容易判断的，但“距离是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)=2 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)=2 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)=2 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₂)+k²+1, (^[(n+2)/2]₂) +[(n-1)/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=x₀x₁¼x_k be a path of length k in G, we shall prove the following two claims.

Claim 1. G-P_k\{x_o} is connected.

Claim 2. G-P_k has at most two components and if G-P_k has two components H, T, then H and T are two Hamiltonian subgraphs and there exist some vertex of H and some vertex of T that they are all adjacent to x₀ and x_k .

Proof of Claim 1. If H, and T be two components of G-P_k\{x_o} (i). If there exists a vertex of P_k\{x_o}=x₁x₂¼x_k that is adjacent to at least a vertex of H and adjacent to at least a vertex of T, then there exist x in H and y in T with d(x,y)=2. We can check that d(x)+d(y)≤2|V(P_k\{x_o})|+|V(H)|+|V(T)|-|{x,y}|≤n+k-3, which contradicts the hypothesis of Theorem. (ii). If each vertex of P_k\{x_o}=x₁x₂¼x_k is not adjacent to any vertex of at least one of {H, T}. Without loss of generality, assume x_h of P_k\{x_o} is not adjacent to any vertex of H and x_h-1 is adjacent to some vertex x of H, then we can check that d(x)+d(x_h) ≤(k+|V(H)\{x}|)+(k-1+|V(T)|≤n+k-2, a contradiction.

Proof of Claim 2. If H, T and Q be three components of G-P_k. (i). If there exists a vertex of P_k=x₀x₁¼x_k that is adjacent to at least a vertex of H and adjacent to at least a vertex of T, then there exist x in H and y in T with d(x,y)=2. We can check inequality (1): d(x)+d(y)≤2(k+1)+|V(H)|+|V(T)|-|{x,y}|≤n-|V(Q)|+k-1, a contradiction. (ii). If each vertex of P_k=x₀x₁¼x_k is at most adjacent to some vertices of one of {H, T, Q}. Without loss of generality, assume x_h is not adjacent to any vertex of H and x_h-1 is adjacent to some vertex x of H, then we can check that d(x)+d(x_h) ≤(k+1+|V(H)|)+(k+1+max{|V(T)|, |V(Q)|})-|{x,x_h}|≤n+k-2, a contradiction. Thus, G-P_k has at most two components H, T. so completing the proof of Claim 2.

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)=2 in H, we have d_H(u)+d_H(v)≥n-1+k-2(k+1)≥n-(k+1)-|V(T)|-1=|V(H)|-1. Lemma 1, H and T have Hamiltonian path. Let y₁y₂¼y_|V(H)| be a Hamiltonian path of H and z₁z₂¼z_|V(T)| be a Hamiltonian path of T. By Claim 1 that G-P_k\{x_o} is connected, so there must exist y_h in H and z_r in T that are adjacent to some vertex of P_k=x₀x₁¼x_k. By the hypothesis of Theorem that d(y_h)+d(z_r)≥n-1+k, so d(y_h)+d(z_r)=[d_Pk(y_h)+d_H(y_h)]+[d_Pk(z_r)+d_T(z_r)]≥n-1+k, this implies d_Pk(y_h)=k+1, d_H(y_h)=|V(H)|-|{y_h}|, d_Pk(z_r)=k+1, d_T(z_r)=|V(T)|-|{ z_r}|, so y_h is adjacent to x₀ and y₁. By d(x₀)+d(y₁)≥n-1+k, there must exist y_i in Hamiltonian path y₁y₂¼y_|V(H)| of H satisfying that y₁ is adjacent to y_i and x₀ is adjacent to y_i-1(The reason is similar to the above). Similarly, there must exist z_j in Hamiltonian path z₁z₂¼z_|V(T)| of T satisfying that z₁ is adjacent to z_j and x_k is adjacent to y_j-1. Since y_i-1 is a end-vertex of Hamiltonian path y_i-1y_i-1¼y₁ y_iy_i+1¼y_|V(H)| of H and z_j-1 is a end-vertex of Hamiltonian path z_jz_j-1¼z₁z_jz_j+1¼z_|V(T)| of T, so completing the proof.

Next, by d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G, we can check that d_G-Pk(u)+d_G-Pk(v)≥n-1+k-2|V(P_k)|≥n-1+k-2(k+1)=(n-k-1)-2 for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G-P_k, so G-P_k has a path of length at least |V(G-P_k)|-1. We consider the following.

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₁y₂¼y_n-k-1 be a Hamiltonian path of G-P_k. Since d(u)≥k+1 for each vertex u in G, so x₀,x_k are all adjacent to at least one vertex of G-P_k. We claim that there exist two distinct vertices y_i,y_j that are adjacent to x₀,x_k, respectively (Otherwise, it is said that x₀,x_k are all only adjacent to a vertex y_r of G-P_k.. In this case, clearly, |N(x₀)|≤|V(P_k)\{x₀}|+|{y_r}|=k+1 and |N(y_r+1)|≤|V(G)\{x₀,x_k,y_r+1}|=n-3, so we can check that d(x₀)+d(y_r+1)≤(k+1)+|V(G)\{x₀,x_k ,y_r+1}|≤n-2+k, a contradiction ). Without loss of generality, assume y_i is adjacent to x₀,and y_j is adjacent to,x_k and let i,j be as small as possible, so both y_i-1,and y_j-1 are all not adjacent to x₀,x_k. Without loss of generality, assume i≤j-1.

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

If i≤j-2. We consider

By d(y_i-1)+d(x₀)≥n-1+k and d(y_j-1)+d(x_k)≥n-1+k, and y_i-1,and y_j-1 are all not adjacent to x₀,x_k, we have d_G-Pk(y_i-1)+d_G-Pk(x₀)≥n-1+k-(k+k-1)=n-k and d_G-Pk(y_j-1)+ d_G-Pk(x_k)≥n-1+k-(k+k-1)=n-k, so we have d_G-Pk(y_i-1)+d_G-Pk(y_j-1)≥n-k or d_G-Pk(x₀)+ d_G-Pk(x_k)≥n-k. We consider the following two cases.

(1). If d_G-Pk(y_i-1)+d_G-Pk(y_j-1)≥n-k.

In this case, we have the following. (i). When y_tÎN_P(y_j-1)∩{y_j,y_j+1,¼,y_n-k}\{y_j}, then y_t-1 is not adjacent to y_i-1( Otherwise, if y_t-1 is adjacent to y_i+1, then the path y_iy_i+1¼ y_j-1y_ty_t+1¼y_n-k and the path y_jy_j+1¼ y_t-1y_i-1y_i-2¼ y₁ partitioned from P that their end-vertices y_i(=x₀) and y_j are adjacent to x₁,x_k, respectively, a contradiction). (ii). When y_tÎN_P(y_j-1)∩{y_i,y_i+1,¼,y_j-1}, then y_t+1 is not adjacent to y_i-1. (iii). When y_tÎN_P(y_j-1)∩{y₁,y₂,¼,y_i-1}, then y_t-1 is not adjacent to y_i-1. Also, clearly y_i-1 is belongs to neither any y_t+1 of (ii) nor any y_t-1 of (iii). So we can check that d_P(y_i-1) ≤|V(G-P*)|-|N_P(y_j-1)\ {y_j}|-|{y_i-1}|≤(n-k-1)-|N_P(y_j-1)\ {y_j}|-|{y_i-1}|, this implies d_G-Pk(y_i-1)+d_G-Pk(y_j-1)≤n-k-1, a contradiction.

(2). If d_G-Pk(x₀)+d_G-Pk(x_k)≥n-k-1.

In this case, if x₀ or x_k is adjacent to y₁ or y_n-k-1, then we complete the proof. If x₀ and x_k are not adjacent to y₁ and y_n-k-1, then clearly, there must exist consecutive two vertices y_h and y_h+1of P that they are adjacent to x₀,x_k, respectively, so completing the proof.

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)=2 in G, we can check that d_H(u)+d_H(v)≥n-1+k-2|V(P_k)\{x_o}|≥n-1+k-2k=n-k-1 for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in H=G-(P_k\{x_o}). By Lemma 1, H=G-(P_k\{x_o}) has Hamiltonian path. Let T=y₁y₂¼y_n-k be a Hamiltonian path of G-P_k\{x_o}. Without loss of generality, assume y_i=x_o. Since G-P_k has not any Hamiltonian path, so y_i-1y_i+1ÏE(G). By d(y_i-1)+d(y_i+1)≥n-1+k. Since both y_i-1,y_i+1 are not adjacent to x_k, so d_T(y_i-1)+d_T(y_i+1)≥n-1+k-2(k-1)=n+1-k. Hence we have d_T(y_i-1)≥(n+1-k)/2 or d_T(y_i+1)≥(n+1-k)/2. Without loss of generality, assume d_T(y_i-1)≥(n+1-k)/2. Then, since x_k is adjacent to some vertex y_j of T, by d(y_j-1)+d(x_k)≥n-1+k, we have d_T(y_j-1)+ d_T(x_k)≥n-1+k-2(k-1)=n+1-k, so d_T(y_j-1)≥(n+1-k)/2 or d_T(x_k)≥(n+1-k)/2. Without loss of generality, assume d_T(y_j-1)≥(n+1-k)/2. By d_T(y_i-1)≥(n+1-k)/2 and d_T(y_j-1)≥(n+1-k)/2, i.e., we have one of the following. (i). When y_tÎN_T(y_j-1)∩{y_j,y_j+1,¼,y_n-k}\{ y_j}, then y_t-1 is not adjacent to y_i-1( Otherwise, if y_t-1 is adjacent to y_i+1, then path y_iy_i+1¼ y_j-1y_t+1y_t+2¼y_n-k and path y_jy_j+1¼ y_ty_i-1y_i-2¼ y₁ partitioned from T that their end-vertices y_i(=x₀) and y_j adjacent to x₁,x_k, respectively, a contradiction). (ii). When y_tÎN_T(y_j-1)∩{y_i,y_i+1,¼,y_j-1}, then y_t+1 is not adjacent to y_i-1. (iii). When y_tÎN_T(y_j-1)∩{y₁,y₂,¼,y_i-1}, then y_t-1 is not adjacent to y_i-1. So we can check that d_T(y_i-1)≤(n-k)- d_T(y_j-1)\ {y_j}-|{y_i-1,y_j-1}|≤n-k-[(n+1-k)/2-1]-2≤(n+1-k)/2-1, a contradiction.

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=x₀x₁¼x_k be a path of length k in G. By d(u)+d(v)≥n+k for each pair of nonadjacent vertices u,v in G, d_H(u)+d_H(v)≥n+k-2|V(P_k)\{x_o}|≥n+k-2k=n-k, so H=G-(P_k\{x_o}) is connected. By Lemma 2, H has Hamiltonian cycle. Let T=y₁y₂¼y_n-k y₁ be a Hamiltonian cycle of G-P_k\{x_o}, if H=G-(P_k\{x_o}) has Hamiltonian cycle or x_k is adjacent to one of {y₁,y_n-k}, the proof is complete. Otherwise, y₁y_n-kÏE(G) and x_k is not adjacent y₁,y_n-k, we have d_T(y₁)+d_T(y_n-k)≥n-1+k-2(k-1)=n-k+1. Since |G-(P_k\{x_o})|=n-k, so there must exist consecutive vertices y_h,y_h+1 that are adjacent to y_n-1,y₁, respectively. So H=G-(P_k\{x_o}) has Hamiltonian cycle, a contradiction.

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（他的博士有苑立平副院长中华全国青年联合会第十一届委员）, On k-path Hamiltonian graphs. Boll. Un. Mat. Ital. (4) 6 (1972), 61--66.

13、Tudor Zamfirescu院士，On k-path hamiltonian graphs and line-graphs. Rend. Sem. Mat. Univ. Padova 46 (1971), 385--389.（看庆贺他的70岁的学术会议见许多著名数学家的相片-有他和Solomon Marcus院士，Imre Bárány院士，János Pach院士，还有前辈级名家Rolf Schneider，Wlodzimierz Kuperberg，以及最近接连获大奖的Karim Adiprasito特别是他最近和June Huh, Eric Katz合作在 Notices Amer. Math. Soc. 发表论文“Hodge theory of matroids 64 (2017), no. 1, 26–30简概”并引起广泛的国际反响，在很多网站都有Karim Adiprasito, June Huh, Eric Katz的这工作Hodge theory for combinatorial geometries发表在Ann. of Math. (2) 188 (2018), no. 2, 381–452的详细全文）

14、Richard Denman, Dalton Tarwater，k-arc Hamilton graphs.Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), pp. 545--556, Lecture Notes in Math., 642, Springer, Berlin, 1978.

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)=2 in G, then G is (K_h# K₁#K_n-h-1).

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₁) is a cut vertex of G, and the vertex set of G to be V(K_h# K₁#K_n-h-1)=V(K_h)∪V(K_n-h-1)∪{u}, the edge set of G to be E(K_h# K₁#K_n-h-1)=E(K_h)∪E(K_n-h-1)∪e*, e* is an edge set of cut vertex u connected to some vertices of K_n-h-1 and some vertices of K_h.

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₀x₁¼x_k be a path of length k in G. By |N(x)∪N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and since d£d(G-P*)+|V(P*)|, where H=G-P*, we have inequality (*): |N_H(x)∪N_H(y)|≥n-d+k-|V(P*)|=(|V(G-P*)|+|V(P*)|)-(d(G-P*)+|V(P*)|)+k-|V(P*)|=|V(G-P*)|-d(G-P*)-1 for any two vertices x,y in H=G-P* with d_G(x,y)=2. Then we consider the following.

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 of P* is adjacent to some vertex y of Q, and x_j+1 is not adjacent to y. Then clearly, x_j+1 is not adjacent to every vertex of one of {T,R}. Hence we can check that |N_H(x_j+1)∪N_H(y)|≤|V(Q)|+max{|V(T),|V(R)|-|{y}|≤|V(H)|-min{|V(T)|, |V(R)|-|{y}|≤|V(H)|-d(H)-2, which contradicts the above inequality (*).

Thus, Claim holds.

Then we consider the following three cases.

Case 1. H is 2-connected.

let P*=x₀x₁¼x_k be a path of length k in G. By |N(x)∪N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and d£d(H)+|V(P*)|, where H=G-P*, we have inequality (*): |N_H(x)∪N_H(y)|≥n-d+k-|V(P*)|=(|V(H)|+|V(P*)|)-(d(H)+|V(P*)|)+k-|V(P*)|=|V(H)|-d(H)-1 for any two vertices x,y in H with d_G(x,y)=2, where H=G-P_*.

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₀,x_k } must be adjacent to at least two vertices of H. Let P=y₁y₂¼y_n-k-1 y₁ be a Hamiltonian cycle of H and y_i,y_j are adjacent to x₀,x_k satisfying that none of {y_i+1,y_i+2¼,y_j-1} are adjacent x_k. By | N_H(y_i-1)∪N_H(x₀)|≥n-d-1 and | N_H(y_j-1)∪N_H(x_k)|≥n-d-1, we have the following. (i). When y_tÎ(N(y_i-1)∪N(x₀))∩{y_j,y_j+1,¼,y_i-1}, then y_t-1 is not adjacent to y_j-1 and x_k ( Otherwise, if y_t-1 is adjacent to y_i-1, then path y_iy_i+1¼ y_j-1y_t+1y_t+2¼y_i-1y_ty_t-1¼ y_j of H that its two end-vertices y_i(=x₀) and y_j adjacent to x₁,x_k, respectively, a contradiction). (ii). When y_tÎ( N_H(y_i-1)∪N_H(x₀))∩{y_i,y_i+1,¼,y_j-1}\{ y_i}, then y_t+1 is not adjacent to y_j-1 and x_k. So we can check that |N_H(y_j-1)∪N_H(x_k)|≤(n-k-1)-| (N_H(y_i-1)∪N_H(x₀))\{y_i}|-|{y_j-1,x_k}|≤(n-k-1)- (n-d-1)-1≤d-k, a contradiction.

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#K₁#K_(n-k-1)-h-1. Since x₀,x_k are at least adjacent to two vertices of H, so we consider the following.

(i). If x₀,x_k are adjacent to two vertices x,y with x in K_h and y in K_(n-k-1)-h-1, then completing the proof.

(ii). If x₀,x_k are at most only adjacent to some vertices of K_h of K_(n-k-1)-h-1. Without loss of generality, x₀,x_k are not adjacent to any vertex of K_(n-k-1)-h-1, then x₀,x_k are all adjacent to every vertex of K_h.

Otherwise, if v of K_h is not adjacent to x₀, 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*\{ x₀,x_k } is adjacent to some vertex of K_h (or K_(n-k-1)-h-1), then x_i is adjacent to every vertex of K_h (or K_(n-k-1)-h-1).

In this case, G is not k-path Hamiltonian and we denote graph G by (K_h#K₁#K_(n-k-1)-h-1)#G[P*], which x₀,x_k are at most all adjacent to every vertex of K_h or K_(n-k-1)-h-1.

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_H(x)∪N_H(y)|≤|V(H)|-|V(T)|-|(x,y}|≤|V(H)|-d(H)-2, which contradicts inequality (*).

(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 x_{i +1} of P* is not adjacent to vertex x in Q. By (ii), x_{i +1} is not adjacent to any vertex of one {R, T}. Hence we can check that | N_H(x)∪N_H(x_i+1)|≤|V(Q)|+max{|V(R )|, |V(T)|}|-|{x}|≤|V(H)|-min{|V(R )|, |V(T)|}-|{x}|≤|V(H)|-d(H)-2, which contradicts inequality (*).

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哈密顿图的条件.

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

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