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����֤��ȴҪ�ü�ҳ������������������������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  on k-Hamiltonian graphs.

����һ��

Theorem 1(Kronk ). 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 ).��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. 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 , Paul Erdös,Tibor Gallai��Gallai�ĵ�ʦKőnig�ĵ�ʦ�ɿɷ�˹��������˹̹����ʦ����������۵ķ�չ�ֺܴ�Ӱ����Gallai�Ĳ�ʿ�ǻ��3�ι�����ѧ����ƥ�˾����𽱵Ĺ�����ѧ������ϯ��, Zhao, Lai, .

Lemma 1(Zhao-Lai-Shao ). 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 ). 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 .) 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-k2)+k2+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(, 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 Pk=x0x1¼xk be a path of length k in G, we shall prove the following two claims.

Claim 1. G-Pk\{xo} is connected.

Claim 2. G-Pk has at most two components and if G-Pk 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 x0 and xk .

Proof of Claim 1. If H, and T be two components of G-Pk\{xo} (i). If there exists a vertex of Pk\{xo}=x1x2¼xk 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(Pk\{xo})|+|V(H)|+|V(T)|-|{x,y}|��n+k-3, which contradicts the hypothesis of Theorem. (ii). If each vertex of Pk\{xo}=x1x2¼xk is not adjacent to any vertex of at least one of {H, T}. Without loss of generality, assume xh of Pk\{xo} is not adjacent to any vertex of H and xh-1 is adjacent to some vertex x of H, then we can check that d(x)+d(xh) ��(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-Pk. (i). If there exists a vertex of Pk=x0x1¼xk 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 Pk=x0x1¼xk is at most adjacent to some vertices of one of {H, T, Q}. Without loss of generality, assume xh is not adjacent to any vertex of H and xh-1 is adjacent to some vertex x of H, then we can check that d(x)+d(xh) ��(k+1+|V(H)|)+(k+1+max{|V(T)|, |V(Q)|})-|{x,xh}|��n+k-2, a contradiction. Thus, G-Pk has at most two components H, T. so completing the proof of Claim 2.

Now, we consider the following cases.

Case 1. G-Pk 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 dH(u)+dH(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 y1y2¼y|V(H)| be a Hamiltonian path of H and z1z2¼z|V(T)| be a Hamiltonian path of T. By Claim 1 that G-Pk\{xo} is connected, so there must exist yh in H and zr in T that are adjacent to some vertex of Pk=x0x1¼xk. By the hypothesis of Theorem that d(yh)+d(zr)��n-1+k, so d(yh)+d(zr)=[dPk(yh)+dH(yh)]+[dPk(zr)+dT(zr)]��n-1+k, this implies dPk(yh)=k+1, dH(yh)=|V(H)|-|{yh}|, dPk(zr)=k+1, dT(zr)=|V(T)|-|{ zr}|, so yh is adjacent to x0 and y1. By d(x0)+d(y1)��n-1+k, there must exist yi in Hamiltonian path y1y2¼y|V(H)| of H satisfying that y1 is adjacent to yi  and x0 is adjacent to yi-1(The reason is similar to the above).  Similarly, there must exist zj in Hamiltonian path z1z2¼z|V(T)| of T satisfying that z1 is adjacent to zj and xk is adjacent to yj-1. Since yi-1 is a end-vertex of Hamiltonian path yi-1yi-1¼y1 yiyi+1¼y|V(H)| of H and zj-1 is a end-vertex of Hamiltonian path zjzj-1¼z1zjzj+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 dG-Pk(u)+dG-Pk(v)��n-1+k-2|V(Pk)|��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-Pk, so G-Pk has a path of length at least |V(G-Pk)|-1. We consider the following.

Case 2. G-Pk is connected..

We consider the following two subcases.

Subcase 2.1. G-Pk has a Hamiltonian path.

Let P=y1y2¼yn-k-1 be a Hamiltonian path of G-Pk. Since d(u)��k+1 for each vertex u in G, so x0,xk are all adjacent to at least one vertex of G-Pk. We claim that there exist two distinct vertices yi,yj that are adjacent to x0,xk, respectively (Otherwise, it is said that x0,xk are all only adjacent to a vertex yr of G-Pk.. In this case, clearly, |N(x0)|��|V(Pk)\{x0}|+|{yr}|=k+1 and |N(yr+1)|��|V(G)\{x0,xk,yr+1}|=n-3, so we can check that d(x0)+d(yr+1)��(k+1)+|V(G)\{x0,xk ,yr+1}|��n-2+k, a contradiction ). Without loss of generality, assume yi is adjacent to x0,and yj is adjacent to,xk and let i,j be as small as possible, so both yi-1,and yj-1 are all not adjacent to x0,xk. 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(yi-1)+d(x0)��n-1+k and d(yj-1)+d(xk)��n-1+k, and yi-1,and yj-1 are all not adjacent to x0,xk, we have dG-Pk(yi-1)+dG-Pk(x0)��n-1+k-(k+k-1)=n-k and dG-Pk(yj-1)+ dG-Pk(xk)��n-1+k-(k+k-1)=n-k, so we have dG-Pk(yi-1)+dG-Pk(yj-1)��n-k or dG-Pk(x0)+ dG-Pk(xk)��n-k. We consider the following two cases.

(1). If dG-Pk(yi-1)+dG-Pk(yj-1)��n-k.

In this case, we have the following. (i). When ytÎNP(yj-1)��{yj,yj+1,¼,yn-k}\{yj}, then yt-1 is not adjacent to yi-1( Otherwise, if yt-1 is adjacent to yi+1, then the path yiyi+1¼ yj-1ytyt+1¼yn-k and the path yjyj+1¼ yt-1yi-1yi-2¼ y1 partitioned from P that their end-vertices yi(=x0) and yj  are adjacent to x1,xk, respectively, a contradiction). (ii). When ytÎNP(yj-1)��{yi,yi+1,¼,yj-1}, then yt+1 is not adjacent to yi-1. (iii). When ytÎNP(yj-1)��{y1,y2,¼,yi-1}, then yt-1 is not adjacent to yi-1. Also, clearly yi-1 is belongs to neither any yt+1 of (ii) nor any yt-1 of (iii). So we can check that dP(yi-1) ��|V(G-P*)|-|NP(yj-1)\ {yj}|-|{yi-1}|��(n-k-1)-|NP(yj-1)\ {yj}|-|{yi-1}|, this implies dG-Pk(yi-1)+dG-Pk(yj-1)��n-k-1, a contradiction.

(2). If dG-Pk(x0)+dG-Pk(xk)��n-k-1.

In this case, if x0 or xk is adjacent to y1 or yn-k-1, then we complete the proof. If x0 and xk are not adjacent to y1 and yn-k-1, then clearly, there must exist consecutive two vertices yh and yh+1of P that they are adjacent to x0,xk, respectively, so completing the proof.

Subcase 2.2. G-Pk has not any Hamiltonian path.

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���ܶ�·-�˶�������

Proof. Let Pk=x0x1¼xk 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, dH(u)+dH(v)��n+k-2|V(Pk)\{xo}|��n+k-2k=n-k, so H=G-(Pk\{xo}) is connected. By Lemma 2, H has Hamiltonian cycle. Let T=y1y2¼yn-k y1 be a Hamiltonian cycle of G-Pk\{xo}, if H=G-(Pk\{xo}) has Hamiltonian cycle or xk is adjacent to one of {y1,yn-k}, the proof is complete. Otherwise, y1yn-kÏE(G) and xk is not adjacent y1,yn-k, we have dT(y1)+dT(yn-k)��n-1+k-2(k-1)=n-k+1. Since |G-(Pk\{xo})|=n-k, so there must exist consecutive vertices yh,yh+1 that are adjacent to yn-1,y1, respectively. So H=G-(Pk\{xo}) 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 .

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�C106.

2�� Kenneth Reid, Carsten Thomassen, Edge sets contained in circuits. Israel J. Math. 24 (1976), no. 3�C4, 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  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�C30�����������㷺�����ʷ��������ܶ���վ����Karim Adiprasito, June Huh, Eric Katz���⹤��Hodge theory for combinatorial geometries������Ann. of Math. (2) 188 (2018), no. 2, 381�C452����ϸȫ����

14��RichardDalton��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(����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 .

����1 (Zhao ). ��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 (Kh# K1#Kn-h-1).

Where Kh and Kn-h-1 are two disjoint complete graphs of orders h and n-h-1, respectively, and u=V(K1) is a cut vertex of G, and the vertex set of G to be V(Kh# K1#Kn-h-1)=V(Kh)��V(Kn-h-1)��{u}, the edge set of G to be E(Kh# K1#Kn-h-1)=E(Kh)��E(Kn-h-1)��e*, e* is an edge set of cut vertex u connected to some vertices of Kn-h-1 and some vertices of Kh.

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*=x0x1¼xk 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 (*): |NH(x)��NH(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 dG(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 |NH(x)��NH(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 |NH(x)��NH(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 xj of P* is adjacent to some vertex y of Q, and xj+1 is not adjacent to y. Then clearly, xj+1 is not adjacent to every vertex of one of {T,R}. Hence we can check that |NH(xj+1)��NH(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*=x0x1¼xk 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 (*): |NH(x)��NH(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 dG(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 {x0,xk } must be adjacent to at least two vertices of H. Let P=y1y2¼yn-k-1 y1 be a Hamiltonian cycle of H and yi,yj are adjacent to x0,xk satisfying that none of {yi+1,yi+2¼,yj-1} are adjacent xk. By | NH(yi-1)��NH(x0)|��n-d-1 and | NH(yj-1)��NH(xk)|��n-d-1, we have the following. (i). When ytÎ(N(yi-1)��N(x0))��{yj,yj+1,¼,yi-1}, then yt-1 is not adjacent to yj-1 and xk ( Otherwise, if yt-1 is adjacent to yi-1, then path yiyi+1¼ yj-1yt+1yt+2¼yi-1ytyt-1¼ yj of H that its two end-vertices yi(=x0) and yj adjacent to x1,xk, respectively, a contradiction). (ii). When ytÎ( NH(yi-1)��NH(x0))��{yi,yi+1,¼,yj-1}\{ yi}, then yt+1 is not adjacent to yj-1 and xk. So we can check that |NH(yj-1)��NH(xk)|��(n-k-1)-| (NH(yi-1)��NH(x0))\{yi}|-|{yj-1,xk}|��(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*\{xo}).

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 |NT(x)��NT(y)|��n-d+k-|V(P*\{xo})|=(|V(T)|+|V(P*)|)-(d(T)+|V(P*\{xo})|)+k-|V(P*\{xo})|=|V(T)|-d(T) for any two vertices x,y in T with dG(x,y)=2, where T=G-(P*\{xo}).

Since H=G-P* is 2-connected, and xo is adjacent to at least two vertices of H, so T=G-(P*\{xo}) 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=Kh#K1#K(n-k-1)-h-1. Since x0,xk are at least adjacent to two vertices of H, so we consider the following.

(i). If x0,xk are adjacent to two vertices x,y with x in Kh and y in K(n-k-1)-h-1, then completing the proof.

(ii). If x0,xk are at most only adjacent to some vertices of Kh of K(n-k-1)-h-1. Without loss of generality, x0,xk are not adjacent to any vertex of K(n-k-1)-h-1, then x0,xk are all adjacent to every vertex of Kh.

Otherwise, if v of Kh is not adjacent to x0, then we can check that |NH(v)��NH(xo)|��|V(H)|-|{v}|-|V(K(n-k-1)-h-1}|��|V(H)|-d(H)-2,, which contradicts inequality (*).

Similarly, if some vertex xi of P*\{ x0,xk } is adjacent to some vertex of Kh (or K(n-k-1)-h-1), then xi is adjacent to every vertex of Kh (or K(n-k-1)-h-1).

In this case, G is not k-path Hamiltonian and we denote graph G by (Kh#K1#K(n-k-1)-h-1)#G[P*], which x0,xk are at most all adjacent to every vertex of Kh 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 xi of P* is adjacent to vertex x in Q and y in R. Then similarly, we can check that | NH(x)��NH(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 xi of P* is adjacent to vertex x in Q and xi +1 of P* is not adjacent to vertex x in Q. By (ii), xi +1 is not adjacent to any vertex of one {R, T}. Hence we can check that  | NH(x)��NH(xi+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���ܶ�ͼ������.

��������צͼ�ĶȺ������Լ����������Ĺ���.

������żͼ�ĶȺ������Լ����������Ĺ���.