3-连通无爪图hamilton连通性的一个定理

《3-连通无爪图hamilton连通性的一个定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cn3-连通无爪图Hamilton连通性的一个定理刘弘，李明楚大连理工大学软件学院，辽宁大连(116023)E-mail：qimokaoshi@163.com摘要：hamilton-连通性问题是图论中重要问题之一。O.Ore已证明了如下的著名定理：对于n阶图G中任意两个不相邻顶点u和v，若满足d(u)+d(v)≥n+1，则G为hamilton-连通的。本文要对无爪图进行讨论，主要证明了：假设G是n阶3-连通无爪图，且设P是任意一对顶点u,v间在G中的最长路。若G−P是hamilton-连通的，−+N(G−P)={

2、u,x,x,v}且N(x)−{x,x,x,u,v}≠φ，则

3、V(P)

4、≥min{5δ−8,n}。P23P3332关键词：3-连通；无爪图；hamilton-连通图中图分类号：TP3931.引言本文只讨论有限简单图G=(V(G),E(G))。用

5、G

6、表示V(G)的基数。如果图G中不含有与K同构的导出子图，则称图G为无爪图。令G为n阶图且r≤n，定义1,3δ(G)=min{

7、∪N(u)

8、:S⊂V(G)且

9、S

10、=r}，我们分别定义δ(G)(或δ)为G中顶点ru∈S最小度、κ(G)为G中连通度。如κ≤α(G[S])，则令δ(S)表示S中任意k对不相邻顶点k在图G

11、中度数之和的最小值；κ>α(G[S])，令δ(S)=κ(n−1)。对于图G的子图H和kV(G)的子集S，我们分别用G−H和G[S]表示V(G)−V(H)的导出子图和S的导出子图；并用N(S)表示H中所有与子集S中顶点相邻的顶点。令d(S)=

12、N(S)

13、且HHHE(H,S)={uv∈E(G):u∈V(H)且v∈S}。如果P=xx...x是图G中的一条路，令G12t+−x=x(1≤i

14、x,x]{x,x}。我们仍将jijijj−1iijijijP(x,x)和P[x,x]看作相应的顶点集。如果图G中存在一条包含G每个顶点的路，则ijij称之为G的hamilton路；如果图G中任意两个顶点u和v间均存在hamilton路，则称G为hamilton-连通的。令H为图G的子图。我们用α(H)表示在G中距离至少为3且属于H3的顶点对的最大值。文中未加定义的概念和记号参见[1]。一般说来，判断一个图是否为hamilton-连通的相当困难，是NP-完全问题[5]。对一般图，这个问题也没有完全解决。这里我们对一个重要的特殊图类无爪图进行讨论。无爪图是

15、一个重要的图类，它包含了线图，而线图本身就是图论中的一个重要图类[6][7]。O.Ore[8]已证明了如下的著名定理：对于n阶图G中任意两个不相邻顶点u和v，若满足d(u)+d(v)≥n+1，则G为hamilton-连通的。目前的主要结果有：n+1定理1(Ore[8])对于n阶图G，若δ≥，则G为hamilton-连通的。2−定理2(LiMingchu[3])设G为α3≤κ(G)−1的n阶3-连通无爪图，则G为hamilton-连通的。-1-http://www.paper.edu.cn定理3(LiMingchu[4])设G为n阶3-连通无爪图，若n≤4

16、δ−4，则G为hamilton-连通的。定理4(LiMingchu[2])设G为n阶3-连通无爪图，若n≤5δ−8，则G为hamilton-连通的。定理5(Wuetal.[9])设G为σ(G)≥n−k+3的n阶κ连通(κ≥3)无爪图，则G为khamilton-连通的。本文要证明如下定理：定理假设G为n阶3-连通无爪图，且设P是任意一对顶点u,v间在G中的最长路。若G−P是hamilton-连通的，N(G−P)={u,x,x,v}且P23−+N(x)−{x,x,x,u,v}≠φ，则

17、V(P)

18、≥min{5δ−8,n}。P33322.引理及主要结论引理2.1

19、[4].若G为n阶3-连通无爪图且G为非hamilton-连通的，令P为非hamilton的最长路，以H表示分支G−P。则在G中存在顶点数为d(H)的独立集D、在P上存P在顶点数为(d(H)−1)的点集T⊂D，使得P∑v∈Dd(v)≤n−dP(H)+2，且

20、V(P)

21、≥∑V∈tdP(v)+

22、T

23、+dP(H)−2其中当v∈T时，有N(v)∩N(H)=φ，N(v)=φ；当u≠v∈T时，N(u)∩N(v)=φ。PH引理2.2假设G为n≤6δ−10阶3-连通无爪图，如G为非hamilton-连通的，则存在两顶点u和v，使其间不存在hamilton路。令P为图G中

24、u和v间最长路。若G−P为hamilton-连通的且N(G−P)={u,x,x,