图中强路圈性质的若干充分条件
摘要
图的路和圈问题是图论中一个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题。图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题。国内外许多学者对此问题作了大量的研究工作。这方面的研究成果和进展可参见文献。其中度条件和邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果。经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体。路的方面包括图的Hamilton路(可迹性),齐次可迹性:最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等。
由于直接研究—般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类。继Beineke1970年发表的关于线图性质的文章之后,人们开始关注包含着线图的无爪图。70年代末80年代初,是研究无爪图的一个非常活跃的时期。关于无爪图方面的部分优秀成果可参考。另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K_(1,4);2)-图等。2005年,刘春房在中定义了一种新的图类-[s,t]-图,即任意s个点之间至少含有t条边。而我在这类[s,t]-图的基础上提出了强-[s,t]图,即任意s个点之间至少含有t条独立边。这类图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用。
本文就是研究强-[s,t]图和一般图中与度有关的强路圈性质。
在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果。
在第二章中,我们主要研究了强-[s,t]图在不同条件下的强路圈性质,得到下面的结果:
定理2.1.4设G是n(n≥6)阶强-[4,2]图,则G是泛圈的。
定理2.1.5设G是n(n≥7)阶强-[4,2]图,则G是完全圈可扩的。
定理2.1.6设G是n(n≥8)阶强-[4,2]图,则G是路可扩的。
定理2.2.4设G是n(n≥8)阶连通强-[5,2]图,则G含有Hamilton路。
定理2.2.5设G是δ(G)≥3的连通,局部连通的强-[5,2]图,则G是完全圈可扩的或者同构于图F。
推论2.2.6设G是δ(G)≥3的n(n＞8)阶连通,局部连通的强-[5,2]图,则G是完全圈可扩的。
定理2.3.3设G是n(n≥3m-1)阶强-[2m,m]图,则G含有Hamilton路。
定理2.3.4设G是n(n≥3m)阶强-[2m,m]图,则G含有Hamilton圈。
在第三章中,讨论了图中在与度有关的条件下关于圈的几个结果:
定理3.8设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥n+k,则G中任意一个满足n/k+2＜|C|＜n的圈C是可扩的。
推论3.9设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥3/2n-2,则G是完全圈可扩的。
定理3.10设G的阶n≥3,如果G中任意一对d(u,ν)=2的顶点u,ν满足d(u)+d(ν)≥n+1,则存在一个顶点x∈{u,ν},过x有各种长度的圈。
在第四章中,讨论了图中在与度有关的条件下关于路的几个结果:
定理4.3设G的阶n≥3,如果G中任意一对不同的顶点u,ν满足d(u)+d(ν)≥n+1,则G是路可扩的。
定理4.4设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥n+1,则G中任意一条满足n/3+1＜|P|＜n的路P可扩的。
The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active.Many practical problems can be attributed to the problem of paths and cycles.What is more,the famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence.Many scholars at home and abroad made a lot of research work on this issue.The research results and progress in this area can be found in literature[38]-[42].The condition of degree and neighborhood unions becomes an important way to study the problems. In this respect,a lot of outstanding achievements have be made.After the development for dozens of years,the contents in properties of graphs' path and cycle become more and more rich and specific.The properties of path include Hamilton path(traceability),longest path,panconnectivity,path extendsibility and so on; the properties of cycle include Hamilton cycle,longest cycle,(vertex-)pancyclicity, vertex-disjoint cycle,cycle extendsibility and so on.
However,we can not deny the fact that it is usually very difficult to study Hamilton problem in those graphs without any restriction.Then we turn to explore the graphs not containing some forbidden subgraphs such as claw-free graphs.The first motivation for studying properties of claw-free graphs apparently appeared from Beincke's characterization of line graphs in[17].However,the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s.Some famous results about clawfree graphs can be seen in[1]-[3],[19]-[31].In addition,the definition of claw-free graph has been extended to several larger graph families in different views,such as quasi-claw-free graphs,almost claw-free graphs,(K_(1,4);2)-graphs etc.In 2005. Liu Chunfang[4]defined a new graph family-[s,t]-graphs,that is,there are at least t edges in every included subgraphs of s vertices in graph G.According to this graph,I defined a new graph family -strong-[s,t]graphs,that is,there are at least t independent edges in every included subgraphs of s vertices in graph G. These graphs can be used in traffic network,communications,the configuration of computer networks,etc.
In this paper,we mainly discuss the properties of graphs' path and cycle in [s,t]-graphs and the properties about degree of graphs' path and cycle in all graphs.
In the first chapter,we give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper.In the meantime,we also give some related research backgrounds and some known results.
In the second chapter,we mainly study the paths and cycles of strong-[s,t] graphs and give the following results:
Theorem2.1.4 If G is a strong-[4,2]graph with |G|≥6,then G is pancyclic.
Theorem2.1.5 If G is a strong-[4,2]graph with |G|≥7,then G is fully cycle extendable.
Theorem2.1.6 If G is a strong-[4,2]graph with |G|≥8,then G is path extendable.
Theorem2.2.4 If G is a connected strong-[5,2]graph with |G|≥8,then G has a Hamilton path.
Theorem2.2.5 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable or G≌F.
Corollary2.2.6 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable.
Theorem2.3.3 If G is a strong-[2m,m]graph with |G|≥3m - 1,then G has a Hamilton path.
Theorem2.3.4 If G is a strong-[2m.,m]graph with |G|≥3m,then G has a Hamilton.cycle.
In the third chapter,we mainly study cycles of all graphs about degree conditions and give the following results:
Theorem3.8 Let G be a graph of order n≥3.If d(u)+d(v)≥n+k for every pair u,v of nonadjacent vertices.,then the every cycle C satisfying n/(k+2)＜|C|＜n is extendable.
Corollary3.9 Let G be a graph of order n≥3.If d(u)+d(v)≥(3n)/2- 2 for every pair u,v of nonadjacent vertices,then G is fully cycle extendable.
Theorem3.10 Let G be a graph order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of d(u,v) = 2,then existing a vertex x∈{u,v} and each integer k with 3≤k≤n,G has a k-cycle C_k such that x∈V(C_k).
In the fourth chapter,we mainly study paths of all graphs about degree conditions and give the following results:
Theorem4.3 Let G be a graph of order n≥3.If d(u)+d(v)≥n+1 for every pair u,v,then G is path extendable.
Theorem4.4 Let G be a graph of order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of nonadjacent vertices,then the every path P satisfying n/3+1＜|P|＜n is extendable.
由于直接研究—般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类。继Beineke1970年发表的关于线图性质的文章之后,人们开始关注包含着线图的无爪图。70年代末80年代初,是研究无爪图的一个非常活跃的时期。关于无爪图方面的部分优秀成果可参考。另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K_(1,4);2)-图等。2005年,刘春房在中定义了一种新的图类-[s,t]-图,即任意s个点之间至少含有t条边。而我在这类[s,t]-图的基础上提出了强-[s,t]图,即任意s个点之间至少含有t条独立边。这类图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用。
本文就是研究强-[s,t]图和一般图中与度有关的强路圈性质。
在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果。
在第二章中,我们主要研究了强-[s,t]图在不同条件下的强路圈性质,得到下面的结果:
定理2.1.4设G是n(n≥6)阶强-[4,2]图,则G是泛圈的。
定理2.1.5设G是n(n≥7)阶强-[4,2]图,则G是完全圈可扩的。
定理2.1.6设G是n(n≥8)阶强-[4,2]图,则G是路可扩的。
定理2.2.4设G是n(n≥8)阶连通强-[5,2]图,则G含有Hamilton路。
定理2.2.5设G是δ(G)≥3的连通,局部连通的强-[5,2]图,则G是完全圈可扩的或者同构于图F。
推论2.2.6设G是δ(G)≥3的n(n＞8)阶连通,局部连通的强-[5,2]图,则G是完全圈可扩的。
定理2.3.3设G是n(n≥3m-1)阶强-[2m,m]图,则G含有Hamilton路。
定理2.3.4设G是n(n≥3m)阶强-[2m,m]图,则G含有Hamilton圈。
在第三章中,讨论了图中在与度有关的条件下关于圈的几个结果:
定理3.8设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥n+k,则G中任意一个满足n/k+2＜|C|＜n的圈C是可扩的。
推论3.9设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥3/2n-2,则G是完全圈可扩的。
定理3.10设G的阶n≥3,如果G中任意一对d(u,ν)=2的顶点u,ν满足d(u)+d(ν)≥n+1,则存在一个顶点x∈{u,ν},过x有各种长度的圈。
在第四章中,讨论了图中在与度有关的条件下关于路的几个结果:
定理4.3设G的阶n≥3,如果G中任意一对不同的顶点u,ν满足d(u)+d(ν)≥n+1,则G是路可扩的。
定理4.4设G的阶n≥3,如果G中任意一对不相邻的顶点u,ν满足d(u)+d(ν)≥n+1,则G中任意一条满足n/3+1＜|P|＜n的路P可扩的。
The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active.Many practical problems can be attributed to the problem of paths and cycles.What is more,the famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence.Many scholars at home and abroad made a lot of research work on this issue.The research results and progress in this area can be found in literature[38]-[42].The condition of degree and neighborhood unions becomes an important way to study the problems. In this respect,a lot of outstanding achievements have be made.After the development for dozens of years,the contents in properties of graphs' path and cycle become more and more rich and specific.The properties of path include Hamilton path(traceability),longest path,panconnectivity,path extendsibility and so on; the properties of cycle include Hamilton cycle,longest cycle,(vertex-)pancyclicity, vertex-disjoint cycle,cycle extendsibility and so on.
However,we can not deny the fact that it is usually very difficult to study Hamilton problem in those graphs without any restriction.Then we turn to explore the graphs not containing some forbidden subgraphs such as claw-free graphs.The first motivation for studying properties of claw-free graphs apparently appeared from Beincke's characterization of line graphs in[17].However,the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s.Some famous results about clawfree graphs can be seen in[1]-[3],[19]-[31].In addition,the definition of claw-free graph has been extended to several larger graph families in different views,such as quasi-claw-free graphs,almost claw-free graphs,(K_(1,4);2)-graphs etc.In 2005. Liu Chunfang[4]defined a new graph family-[s,t]-graphs,that is,there are at least t edges in every included subgraphs of s vertices in graph G.According to this graph,I defined a new graph family -strong-[s,t]graphs,that is,there are at least t independent edges in every included subgraphs of s vertices in graph G. These graphs can be used in traffic network,communications,the configuration of computer networks,etc.
In this paper,we mainly discuss the properties of graphs' path and cycle in [s,t]-graphs and the properties about degree of graphs' path and cycle in all graphs.
In the first chapter,we give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper.In the meantime,we also give some related research backgrounds and some known results.
In the second chapter,we mainly study the paths and cycles of strong-[s,t] graphs and give the following results:
Theorem2.1.4 If G is a strong-[4,2]graph with |G|≥6,then G is pancyclic.
Theorem2.1.5 If G is a strong-[4,2]graph with |G|≥7,then G is fully cycle extendable.
Theorem2.1.6 If G is a strong-[4,2]graph with |G|≥8,then G is path extendable.
Theorem2.2.4 If G is a connected strong-[5,2]graph with |G|≥8,then G has a Hamilton path.
Theorem2.2.5 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable or G≌F.
Corollary2.2.6 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable.
Theorem2.3.3 If G is a strong-[2m,m]graph with |G|≥3m - 1,then G has a Hamilton path.
Theorem2.3.4 If G is a strong-[2m.,m]graph with |G|≥3m,then G has a Hamilton.cycle.
In the third chapter,we mainly study cycles of all graphs about degree conditions and give the following results:
Theorem3.8 Let G be a graph of order n≥3.If d(u)+d(v)≥n+k for every pair u,v of nonadjacent vertices.,then the every cycle C satisfying n/(k+2)＜|C|＜n is extendable.
Corollary3.9 Let G be a graph of order n≥3.If d(u)+d(v)≥(3n)/2- 2 for every pair u,v of nonadjacent vertices,then G is fully cycle extendable.
Theorem3.10 Let G be a graph order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of d(u,v) = 2,then existing a vertex x∈{u,v} and each integer k with 3≤k≤n,G has a k-cycle C_k such that x∈V(C_k).
In the fourth chapter,we mainly study paths of all graphs about degree conditions and give the following results:
Theorem4.3 Let G be a graph of order n≥3.If d(u)+d(v)≥n+1 for every pair u,v,then G is path extendable.
Theorem4.4 Let G be a graph of order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of nonadjacent vertices,then the every path P satisfying n/3+1＜|P|＜n is extendable.
引文
[1]L.Clark,Hamiltonian properties of connected locally connected graphs[J].Congr.Numer.32(1981)199-204.
[2]C.Q.Zhang,Cycles of given length in some K_(1,3)-free graphs[J].Discrete Math,78(1989)307-313.
[3]A.Ainouche,H.J.Broerama,H.J.Veldman,Remarks on hamiltonian properties of claw-free graphs[J].Ars Combinatoria 29C(1990)110-121.
[4]刘春房,王江鲁.[s,t]-图及其Hamilton性[J].山东师范大学学报(自然科学版),2005,20(1)7-8.
[5]蔺厚元,孔淑霞.3-连通[5,3]-图的Hamilton性[1J].内蒙古师范大学学报:自然科学汉文版,2005,34(3):288-289
[6]W.Jianglu and Z.Yongjin,Path extensibility of connected,locally 2-connected,K_(1,3)-free graphs[J].Systems Science and Mathematical Sciences,10(1997)267-274.
[7]G.R.T.Hendry,Extending cycles in graphs[J].Discrete Math.85(1990)59-72.
[8]S.Brandt,G.Chen,R.Faudree,R.J.Gould and L.Lesniak,Degree conditions for 2-factors[J].Graph Theory,24(1997) 165-173.
[9]K.Corr(?)di and A.Hajnal,On the maximal number of independent circuits in graph[J].Acta Math.Acad.Sci.Hungar.14(1963) 423-439.
[10]P.Justcsen,On independent circuits in finite graphs and a conjecture of Erd(o|¨)s and P(?)sa[J].Annals of Discrete Math,41(1989) 299-306.
[11]H.Enomoto,On the existence of disjoint cycles in a gvaph[Jj.Combinatorica.18 (1988) 487-492.
[12]J.-C.Bermond,C.Thomassen,Cycles in digraphs-a survey[J].Graph Theory 5(1981)1-43.
[13]G.A.Dirac,Some theorems on abstract graphs[J].Proc.London Matb.Soc.2(1952),69-81.
[14]O.Ore,Note on hamilton circuits[J].Amer.Math.Monthly 67(1960),55.
[15]R.J.Gould,Advances on the hamiltonian problem-a survey[J].Graphs and Combin.19(2003)7-52.
[16]S.Brandt,9-connected claw-free graphs are hamilton-connected[J].Combin Theory Ser.B75(1999)167-173.
[17]L.W.Beineke,Characterizations of derived graphs[J].Combin.Theory Ser.B9(1970)129-135.
[18]G.Fan,New sufficient conditions for cycles in graphs[J].Combin Theory Ser.B37(1984)221-227.
[19]Mingchu Li,Hamiltonian connected claw-free graphs[J].Graphs and Combin.20(2004)341-362.
[20]C.Thomassen,Reflections on graph theory[J].Graph Theory 10(1986)309-324.
[21]S.Goodman,S.Hedetniemi,Sufficient conditions for a graph to be hamiltonian[J].Combin.Theory Ser.B 16(1974)175-180.
[22]R.J.Gouid,M.S.Jacobson,Forbidden subgraphs and the hamiltonian properties in graphs[J].Discrete Math.42(1982)189-196.
[23]S.Olariu,The strong perfect graph conjecture for pan-free graphs[J].Combin.Theory Ser.B 47(1989)187-191.
[24]L.Nebesk(?),On the existence of 1-factors in partial squares of graphs[J].Czechoslovak Math.29(1979)349-352.
[25]Edge-hamilton property in regular 2-connected graphs[J].Discrete Math.82(1990)25-34.
[26]S.Poljak,A note on stable sets and coloring of graphs[J].Comment.Math.Univ.Carolin.15(1974)307-309.
[27]Zden(?)k Ryj(?)ek,On a closure concept in claw-free graphs[J].Combin.Theory Ser.B.70(1997)217-224.
[28]Stephan Brandt,Odile Favaron,Zden(?)k Ryj(?)ek,Closure and stable hamiltonian properties in claw-free graphs[J].Graph Theory 34(2000)30-41.
[29]B(?)la Bollo(?)s,Zden(?)k Ry(?)ek,Closure and hamiltonian-connectivity of clawfree graphs[J].Discrete Math.195(1999)67-80.
[30]Hajo Broersma,Zden(?)k Ryj(?)ek,Ingo Schiermeyer,Closure concepts:a survey[J].Graphs and Combin.16(2000) 17-48.
[31]Alexander Kilmans,On graph closures[J].Discrete Math.271(2003)141-168.
[32]R.Faudree,E.Flandrin,Z.Ryj(?)ek,Claw-free graphs - a survey[J].Discrete Math.164(1997)87-147.
[33]Rao Li,Hamiltonicity of 2-connected quasi claw-free graphs.Discrete Math[J].283(2004)145-150.
[34]Rao Li,Hamiltoncity of 3-connected quasi claw-free graphs.Discrete Math[J].265(2003)393-399.
[35]Chuanping Chen,Ame]Harkat-Benhamdine,Hao Li,Distance-dominating cycles in quasi claw-free graphs[J].Graphs and Combin.15(1999)279-285.
[36]Z.Ryj(?)ek,Almost claw-free graphs[J].Graph Theory 18(1994)469-477.
[37]Mingchu Li,Longgest cycles in almost claw-free graphs[J].Graphs and combin.16(2000)177-198.
[38]Mingquan zhan,Neighborhood intersections and hamiltonicity in almost claw-free graphs[J].Discrete Math.243(2002)171-185.
[39]O.Favaron,E.Flandrin,Hao Li,Z.Ryj(?)ek,Shortest walks in almost clawfree graphs[J].Ars Combin.42(1996)223-232.
[40]Rao Li,R.H.Schellp,Hamiltonicity of(K_(1,4),K_(1,4)+e)-free graphs[J].Discrete Math.245(2002)195-202.
[41]Rao Li,R.H.Schelpb,Every3-connected distance claw-free graph is Hamiltonconnected [J].Discrete Mathematics.268(2003) 185-197.
[42]滕延燕,尤海燕,连通、几乎局部连通的拟无爪图是完全圈可扩的[J].山东师范大学学报(自然科学版),4(2002)5-8.
[43]王江鲁,爪心独立图的可扩圈[J].系统工程理论与实践,9(1997)68-70.
[44]雷泓吴,李敏,王江鲁,连通,局部2-连通[4,2]图中的Hamilton圈[J].内蒙古师范大学学报(自然科学版),Sep.2006,Vol.35,No.3,285-287.
[45]李敏,曲晓英,王江鲁,连通[5,3]-图中的最长路(圈)[J].山东理工大学学报(自然科学版),Feb.2006,Vol.20,No.2,20-22.
[46]田丰,施容华,一类新的泛圈图[J].系统科学与数学.6(1986)258-262.
[47]J.A.Bondy and U.S.R.Murty,Graph theory with applications[M].Macmillan London and Elsevier,New York,1976.
[48]尤海燕,含有某些禁用子图的图的相关路问题[D].济南:山东师范大学硕士毕业论文,2003.
[49]蔺厚元,(K_(1,4);2)-图的哈密顿性[D].济南:山东师范大学硕士毕业论文,2005.
[50]李敏,[s,t]-图的路和圈问题[D].济南:山东师范大学硕士毕业论文,2007.
[2]C.Q.Zhang,Cycles of given length in some K_(1,3)-free graphs[J].Discrete Math,78(1989)307-313.
[3]A.Ainouche,H.J.Broerama,H.J.Veldman,Remarks on hamiltonian properties of claw-free graphs[J].Ars Combinatoria 29C(1990)110-121.
[4]刘春房,王江鲁.[s,t]-图及其Hamilton性[J].山东师范大学学报(自然科学版),2005,20(1)7-8.
[5]蔺厚元,孔淑霞.3-连通[5,3]-图的Hamilton性[1J].内蒙古师范大学学报:自然科学汉文版,2005,34(3):288-289
[6]W.Jianglu and Z.Yongjin,Path extensibility of connected,locally 2-connected,K_(1,3)-free graphs[J].Systems Science and Mathematical Sciences,10(1997)267-274.
[7]G.R.T.Hendry,Extending cycles in graphs[J].Discrete Math.85(1990)59-72.
[8]S.Brandt,G.Chen,R.Faudree,R.J.Gould and L.Lesniak,Degree conditions for 2-factors[J].Graph Theory,24(1997) 165-173.
[9]K.Corr(?)di and A.Hajnal,On the maximal number of independent circuits in graph[J].Acta Math.Acad.Sci.Hungar.14(1963) 423-439.
[10]P.Justcsen,On independent circuits in finite graphs and a conjecture of Erd(o|¨)s and P(?)sa[J].Annals of Discrete Math,41(1989) 299-306.
[11]H.Enomoto,On the existence of disjoint cycles in a gvaph[Jj.Combinatorica.18 (1988) 487-492.
[12]J.-C.Bermond,C.Thomassen,Cycles in digraphs-a survey[J].Graph Theory 5(1981)1-43.
[13]G.A.Dirac,Some theorems on abstract graphs[J].Proc.London Matb.Soc.2(1952),69-81.
[14]O.Ore,Note on hamilton circuits[J].Amer.Math.Monthly 67(1960),55.
[15]R.J.Gould,Advances on the hamiltonian problem-a survey[J].Graphs and Combin.19(2003)7-52.
[16]S.Brandt,9-connected claw-free graphs are hamilton-connected[J].Combin Theory Ser.B75(1999)167-173.
[17]L.W.Beineke,Characterizations of derived graphs[J].Combin.Theory Ser.B9(1970)129-135.
[18]G.Fan,New sufficient conditions for cycles in graphs[J].Combin Theory Ser.B37(1984)221-227.
[19]Mingchu Li,Hamiltonian connected claw-free graphs[J].Graphs and Combin.20(2004)341-362.
[20]C.Thomassen,Reflections on graph theory[J].Graph Theory 10(1986)309-324.
[21]S.Goodman,S.Hedetniemi,Sufficient conditions for a graph to be hamiltonian[J].Combin.Theory Ser.B 16(1974)175-180.
[22]R.J.Gouid,M.S.Jacobson,Forbidden subgraphs and the hamiltonian properties in graphs[J].Discrete Math.42(1982)189-196.
[23]S.Olariu,The strong perfect graph conjecture for pan-free graphs[J].Combin.Theory Ser.B 47(1989)187-191.
[24]L.Nebesk(?),On the existence of 1-factors in partial squares of graphs[J].Czechoslovak Math.29(1979)349-352.
[25]Edge-hamilton property in regular 2-connected graphs[J].Discrete Math.82(1990)25-34.
[26]S.Poljak,A note on stable sets and coloring of graphs[J].Comment.Math.Univ.Carolin.15(1974)307-309.
[27]Zden(?)k Ryj(?)ek,On a closure concept in claw-free graphs[J].Combin.Theory Ser.B.70(1997)217-224.
[28]Stephan Brandt,Odile Favaron,Zden(?)k Ryj(?)ek,Closure and stable hamiltonian properties in claw-free graphs[J].Graph Theory 34(2000)30-41.
[29]B(?)la Bollo(?)s,Zden(?)k Ry(?)ek,Closure and hamiltonian-connectivity of clawfree graphs[J].Discrete Math.195(1999)67-80.
[30]Hajo Broersma,Zden(?)k Ryj(?)ek,Ingo Schiermeyer,Closure concepts:a survey[J].Graphs and Combin.16(2000) 17-48.
[31]Alexander Kilmans,On graph closures[J].Discrete Math.271(2003)141-168.
[32]R.Faudree,E.Flandrin,Z.Ryj(?)ek,Claw-free graphs - a survey[J].Discrete Math.164(1997)87-147.
[33]Rao Li,Hamiltonicity of 2-connected quasi claw-free graphs.Discrete Math[J].283(2004)145-150.
[34]Rao Li,Hamiltoncity of 3-connected quasi claw-free graphs.Discrete Math[J].265(2003)393-399.
[35]Chuanping Chen,Ame]Harkat-Benhamdine,Hao Li,Distance-dominating cycles in quasi claw-free graphs[J].Graphs and Combin.15(1999)279-285.
[36]Z.Ryj(?)ek,Almost claw-free graphs[J].Graph Theory 18(1994)469-477.
[37]Mingchu Li,Longgest cycles in almost claw-free graphs[J].Graphs and combin.16(2000)177-198.
[38]Mingquan zhan,Neighborhood intersections and hamiltonicity in almost claw-free graphs[J].Discrete Math.243(2002)171-185.
[39]O.Favaron,E.Flandrin,Hao Li,Z.Ryj(?)ek,Shortest walks in almost clawfree graphs[J].Ars Combin.42(1996)223-232.
[40]Rao Li,R.H.Schellp,Hamiltonicity of(K_(1,4),K_(1,4)+e)-free graphs[J].Discrete Math.245(2002)195-202.
[41]Rao Li,R.H.Schelpb,Every3-connected distance claw-free graph is Hamiltonconnected [J].Discrete Mathematics.268(2003) 185-197.
[42]滕延燕,尤海燕,连通、几乎局部连通的拟无爪图是完全圈可扩的[J].山东师范大学学报(自然科学版),4(2002)5-8.
[43]王江鲁,爪心独立图的可扩圈[J].系统工程理论与实践,9(1997)68-70.
[44]雷泓吴,李敏,王江鲁,连通,局部2-连通[4,2]图中的Hamilton圈[J].内蒙古师范大学学报(自然科学版),Sep.2006,Vol.35,No.3,285-287.
[45]李敏,曲晓英,王江鲁,连通[5,3]-图中的最长路(圈)[J].山东理工大学学报(自然科学版),Feb.2006,Vol.20,No.2,20-22.
[46]田丰,施容华,一类新的泛圈图[J].系统科学与数学.6(1986)258-262.
[47]J.A.Bondy and U.S.R.Murty,Graph theory with applications[M].Macmillan London and Elsevier,New York,1976.
[48]尤海燕,含有某些禁用子图的图的相关路问题[D].济南:山东师范大学硕士毕业论文,2003.
[49]蔺厚元,(K_(1,4);2)-图的哈密顿性[D].济南:山东师范大学硕士毕业论文,2005.
[50]李敏,[s,t]-图的路和圈问题[D].济南:山东师范大学硕士毕业论文,2007.