［s，t］-图的路和圈问题
摘要
路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域。关于路和圈的进展，已经取得了长足的发展，这方面的研究成果和进展可参见文献[13]-[16]。事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题。经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体。路的方面包括图的Hamilton-路(可迹性)，最长路，Hamilton连通，泛连通，路可扩等等；圈的方面包括图的Hamilton圈，最长圈，(点)泛圈，完全圈可扩，点不交的圈，圈覆盖等等。
由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类。继Beineke1968，1970年发表的关于线图性质的两篇文章[17]-[18]之后，人们开始关注包含着线图的无爪图。70年代末80年代初，是研究无爪图的一个非常活跃的时期。关于无爪图方面的部分优秀成果可参考[2]-[4]，[19]-[33]。另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K_(1，4)；2)-图，DCT图等。关于点不交的圈也是人们热衷的一个问题，一些成果可参考[9]-[12]。2005年，刘春房在[5]中定义了一种新的图类-[s，t]-图，即任意s个点之间至少含有t条边，这类图的特点是其边的分布比较均匀，因而在交通网络，通信系统，计算机的网络配置等方面有着很典型的应用。本文就是研究[s，t]-图的路圈性质。
在第一章中，我们主要介绍了本文的研究背景以及已有的一些结果，以及文章中所涉及的一些概念和术语符号。
在第二章中，我们具体讨论了[s，t]-图在不同连通度下关于路圈的几个结果：
定理2．1．3设G是κ-连通的[κ+2，1]-图，则G含Hamilton路。
定理2．1．4设G是κ-连通的[κ+1，1]-图，则G含Hamilton圈。
定理2．2．1设G是n(n≥6)阶连通[5，3]-图，则G中最长路的长度不小于n-2，且路长的界是紧的。
定理2．2．2设G是n(n≥7)阶连通[5，3]-图，则G中最长圈的长度不小于[n／2]，此界是最好可能的。
定理2．3．2 2-连通[5，3]-图或者含有Hamilton圈或者同构于D，其中D∈{K_(2，3)，K_(1，1，3)，K_(2，4)，K_(1，1，4)}，或者D是图2．3．1-图2．3．10中的图。
推论2．3．3设G是顶点数不小于8且δ(G)≥3的2-连通[5，3]-图，则G含有Hamilton圈。
在第三章中，研究了[4，2]-图的路可扩性，得到下面的结果：
定理3．5设G是连通，局部2-连通的[4，2]-图，或者|G|同构于K_(1，1，1，3)，或者|G|是路可扩的。
在第四章中，研究了[5，3]-图的圈可扩性，证明了下面的结果：
定理4．3设G是δ(G)≥3的连通，局部连通[5，3]-图，则G是完全圈可扩的，或者G≌F(F见图4．3)。
推论4．4设G是δ(G)≥3，|G|≥8的连通，局部连通[5，3]-图，则G是完全圈可扩的。
在第五章中，研究了[4，2]-图的点不交圈，证明了下面的结果：
定理5．5假设G是n(n≥3k+2)阶并且σ_2(G)≥3κ的[4，2]-图，则G含有κ个点不交的圈。
Paths and cycles are two basic structures of graphs. In fact, many practical problems can be attributed to the problem of paths and cycles. Therefore, the research about them is very active. What is more, the famous Hamilton problem is about paths and cycles of graph in essence. 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 Beineke's characterization of line graphs in [17]-[18]. 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 claw-free graphs can be seen in [2]-[4], [19]-[34]. 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, ahnost claw-free graphs, (K_(1,4);2)-graphs, DCT graphs etc. Also, there are a lot of good results about vertex-disjoint cycles in [17]-[18]. Liu Chunfang [5] defmed 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. [s,t]-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.
In the first chapter, we give some related research backgrounds and some known results. In the meantime, we also give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper.
In the second chapter, we mainly study the paths and cycles of [s,t]-graphs and give the following results:
Theorem2.1.3 If G is a k-connected [k+2, 1]-graph, then G has a Hamilton path.
Theorem2.1.4 If G is a k-connected [k+1, 1]-graph, then G has a Hamilton cycle.
Theorem2.2.1 If G is a connected [5,3]-graph with |G|=n≥6, then the longest path of G is at least n-2. Moreover, n-2 is best possible.
Theorem2.2.2 If G is a connected [5,3]-graph with |G|=n≥7, then the longest cycle of G is at least [n/2]. Moreover, [n/2] is best possible.
Theorem2.3.2 If G is a 2-connected [5,3]-graph, then G has a Hamilton cycle, or G≌D, where D∈{K_(2,3), K_(1,1,3), K_(2,4), K_(1,1,4)}, or D is one of the graphs from graph2.3.1 to graph2.3.10.
Corollary2.3.3 If G is a 2-connected [5,3]-graph with |G|≥8 andδ(G)≥3, then G has a Hamilton cycle.
In the third chapter, we mainly obtain the result as follows:
Theorem 3.5 If G is a connected, locally 2-connected [4, 2]-graph, then G≌K_(1,1,1,3) or G is path extendable.
In the fourth chapter, we mainly give some corresponding results of fully cycle extendence:
Theorem 4.3 If G is a connected, locally connected [5, 3]-graph withδ(G)≥3, then G≌F or G is fully cycle extendable.
Corollary 4.4 If G is a connected, locally connected [5, 3]-graph withδ(G)≥3 and |G|≥8, then G is fully cycle extendable.
In the last chapter, we give the following result about vertex-disjoint cycles in [4,2]-graph:
Theorem 5.5 Let G be a [4, 2]-graph, suppose |G|=n≥3k + 2 andσ2(G)≥3k. Then G contains k vertex-disjoint cycles.
由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类。继Beineke1968，1970年发表的关于线图性质的两篇文章[17]-[18]之后，人们开始关注包含着线图的无爪图。70年代末80年代初，是研究无爪图的一个非常活跃的时期。关于无爪图方面的部分优秀成果可参考[2]-[4]，[19]-[33]。另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K_(1，4)；2)-图，DCT图等。关于点不交的圈也是人们热衷的一个问题，一些成果可参考[9]-[12]。2005年，刘春房在[5]中定义了一种新的图类-[s，t]-图，即任意s个点之间至少含有t条边，这类图的特点是其边的分布比较均匀，因而在交通网络，通信系统，计算机的网络配置等方面有着很典型的应用。本文就是研究[s，t]-图的路圈性质。
在第一章中，我们主要介绍了本文的研究背景以及已有的一些结果，以及文章中所涉及的一些概念和术语符号。
在第二章中，我们具体讨论了[s，t]-图在不同连通度下关于路圈的几个结果：
定理2．1．3设G是κ-连通的[κ+2，1]-图，则G含Hamilton路。
定理2．1．4设G是κ-连通的[κ+1，1]-图，则G含Hamilton圈。
定理2．2．1设G是n(n≥6)阶连通[5，3]-图，则G中最长路的长度不小于n-2，且路长的界是紧的。
定理2．2．2设G是n(n≥7)阶连通[5，3]-图，则G中最长圈的长度不小于[n／2]，此界是最好可能的。
定理2．3．2 2-连通[5，3]-图或者含有Hamilton圈或者同构于D，其中D∈{K_(2，3)，K_(1，1，3)，K_(2，4)，K_(1，1，4)}，或者D是图2．3．1-图2．3．10中的图。
推论2．3．3设G是顶点数不小于8且δ(G)≥3的2-连通[5，3]-图，则G含有Hamilton圈。
在第三章中，研究了[4，2]-图的路可扩性，得到下面的结果：
定理3．5设G是连通，局部2-连通的[4，2]-图，或者|G|同构于K_(1，1，1，3)，或者|G|是路可扩的。
在第四章中，研究了[5，3]-图的圈可扩性，证明了下面的结果：
定理4．3设G是δ(G)≥3的连通，局部连通[5，3]-图，则G是完全圈可扩的，或者G≌F(F见图4．3)。
推论4．4设G是δ(G)≥3，|G|≥8的连通，局部连通[5，3]-图，则G是完全圈可扩的。
在第五章中，研究了[4，2]-图的点不交圈，证明了下面的结果：
定理5．5假设G是n(n≥3k+2)阶并且σ_2(G)≥3κ的[4，2]-图，则G含有κ个点不交的圈。
Paths and cycles are two basic structures of graphs. In fact, many practical problems can be attributed to the problem of paths and cycles. Therefore, the research about them is very active. What is more, the famous Hamilton problem is about paths and cycles of graph in essence. 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 Beineke's characterization of line graphs in [17]-[18]. 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 claw-free graphs can be seen in [2]-[4], [19]-[34]. 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, ahnost claw-free graphs, (K_(1,4);2)-graphs, DCT graphs etc. Also, there are a lot of good results about vertex-disjoint cycles in [17]-[18]. Liu Chunfang [5] defmed 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. [s,t]-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.
In the first chapter, we give some related research backgrounds and some known results. In the meantime, we also give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper.
In the second chapter, we mainly study the paths and cycles of [s,t]-graphs and give the following results:
Theorem2.1.3 If G is a k-connected [k+2, 1]-graph, then G has a Hamilton path.
Theorem2.1.4 If G is a k-connected [k+1, 1]-graph, then G has a Hamilton cycle.
Theorem2.2.1 If G is a connected [5,3]-graph with |G|=n≥6, then the longest path of G is at least n-2. Moreover, n-2 is best possible.
Theorem2.2.2 If G is a connected [5,3]-graph with |G|=n≥7, then the longest cycle of G is at least [n/2]. Moreover, [n/2] is best possible.
Theorem2.3.2 If G is a 2-connected [5,3]-graph, then G has a Hamilton cycle, or G≌D, where D∈{K_(2,3), K_(1,1,3), K_(2,4), K_(1,1,4)}, or D is one of the graphs from graph2.3.1 to graph2.3.10.
Corollary2.3.3 If G is a 2-connected [5,3]-graph with |G|≥8 andδ(G)≥3, then G has a Hamilton cycle.
In the third chapter, we mainly obtain the result as follows:
Theorem 3.5 If G is a connected, locally 2-connected [4, 2]-graph, then G≌K_(1,1,1,3) or G is path extendable.
In the fourth chapter, we mainly give some corresponding results of fully cycle extendence:
Theorem 4.3 If G is a connected, locally connected [5, 3]-graph withδ(G)≥3, then G≌F or G is fully cycle extendable.
Corollary 4.4 If G is a connected, locally connected [5, 3]-graph withδ(G)≥3 and |G|≥8, then G is fully cycle extendable.
In the last chapter, we give the following result about vertex-disjoint cycles in [4,2]-graph:
Theorem 5.5 Let G be a [4, 2]-graph, suppose |G|=n≥3k + 2 andσ2(G)≥3k. Then G contains k vertex-disjoint cycles.
引文
[1] J. A. Bondy and U. S. R. Murty, Graph theory with applications. Macmillan London and Elsevier, New York, 1976.
[2] L. Clark, Hamiltonian properties of connected locally connected graphs. Congr. Numer. 32(1981)199-204.
[3] C. Q. Zhang, Cycles of given length in some K_(1,3)-free graphs. Discrete Math, 78(1989)307-313.
[4] A. Ainouche, H. J. Broerama, H. J. Veldman, Remarks on hamiltonian properties of claw-free graphs. Ars Combinatoria 29C(1990)110-121.
[5] 刘春房，王江鲁．[s，t]-图及其Hamilton性[J]．山东师范大学学报(自然科学版)，2005，20(1)7-8．
[6] 蔺厚元，孔淑霞．3-连通[5，3]-图的Hamilton性[J]．内蒙古师范大学学报：自然科学汉文版，2005，34(3)：288-289
[7] 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.
[8] G. R. T. Hendry, Extending cycles in graphs, Discrete Math. [J]. 85(1990)59-72.
[9] S. Brandt, G. Chen, R. Faudree, R. J. Gould and L. Lesniak: Degree conditions for 2factors, J. Graph Theory, 24 (1997) 165-173.
[10] K. Corradi and A. Hajnal: On the maximal number of independent circuits in graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423-439.
[11] P. Justesen: On independent circuits in finite graphs and a conjecture of Erdos and Posa, Annals of Discrete Math., 41 (1989) 299-306.
[12] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica, 18 (1988) 487-492.
[13] J.-C. Bermond, C.Thomassen, Cycles in digraphs - a survey. J. Graph Theory 5(1981)1-43.
[14] R. J. Gould, Updating the hamiltonian problem - a survey. J. Graph Theory 15(1991)121-157.
[15] J. A. Bondy, Basic graph theory - paths and cycles. Handbook of combinatorics, Vol. I, pp. 5-110, Amsterdam: Elsevier 1995.
[16] R. J. Gould, Advances on the hamiltonian problem - a survey. Graphs and Combin. 19(2003)7-52.
[17] L. W. Beineke, Derived graphs and digraphs. Beitrage zur Graphentheorie (Teubner, Leipzig, 1968).
[18] L. W. Beineke, Characterizations of derived graphs. J. Combin. Theory Ser. B 9(1970)129-135.
[19] D. P. Sumner, J. I. Moore, Domination perfect graphs. Notices Amer. Math. Soc. 26(1979)A-569.
[20] Mingchu Li, Hamiltonian connected claw-free graphs. Graphs and Combin. 20(2004)341-362.
[21] C. Thomassen, Reflections on graph theory. J. Graph Theory 10(1986)309-324.
[22] S. Goodman, S. Hedetniemi, Sufficient conditions for a graph to be hamiltonian. J. Combin. Theory Ser. B 16(1974)175-180.
[23] D. Duffus, M. S. Jacobson, R. J. Gould, Forbidden subgraphs and the hamiltonian theme, in: The Theory and Applications of Graphs(Kalamazoo, Mich. 1980, Wiley, New York, 1981)297-316.
[24] J. F. Maurras, Polytopes a sommets dans {0, 1}. These de Doctorat d'Etat, Universite Paris 7.
[25] S. Olariu, The strong perfect graph conjecture for pan-free graphs. J. Combin. Theory Set. B 47(1989)187-191.
[26] L. Nebesky, On the existence of 1-factors in partial squares of graphs. Czechoslovak Math. J. 29(1979)349-352.
[27] M. Sekanina, On an ordering of the set of vertices of a connected graph. Spisy Prirod. Fak. Univ. Brno (1960)137-141.
[28] S. Poljak, A note on stable sets and coloring of graphs. Comment. Math. Univ. Carolin. 15(1974)307-309.
[29] Zdenek Ryjacek, On a closure concept in claw-free graphs. J. Combin. Theory Ser. B. 70(1997)217-224.
[30] Stephan Brandt, Odile Favaron, Zdenek Ryjacek, Closure and stable hamiltonian properties in claw-free graphs. J. Graph Theory 34(2000)30-41.
[31] Bela Bolloas, Zdenek Ryjaek, Closure and hamiltonian-connectivity of claw-free graphs. Discrete Math. 195(1999)67-80.
[32] Hajo Broersma, Zdenek Ryjacek, Ingo Schiermeyer, Closure concepts: a survey. Graphs and Combin. 16(2000) 17-48.
[33] Alexander Kilmans, On graph closures. Discrete Math. 271(2003)141-168.
[34] R. Faudree, E. Flandrin, Z. Ryjacek, Claw-free graphs-a survey. Discrete Math. 164(1997)87-147.
[35] Rao Li, Hamiltonicity of 2-connected quasi claw-free graphs. Discrete Math. 283(2004)145-150.
[36] Rao Li, Hamiltoncity of 3-connected quasi claw-free graphs. Discrete Math. 265(2003)393-399.
[37] Chuanping Chen, Amel Harkat-Benhamdine, Hao Li, Distance-dominating cycles in quasi claw-free graphs. Graphs and Combin. 15(1999)279-285.
[38] Z. Ryjacek, Almost claw-free graphs. J. Graph Theory 18(1994)469-477.
[39] Mingchu Li, Longgest cycles in almost claw-free graphs. Graphs and combin. 16(2000)177-198.
[40] Mingquan zhan, Neighborhood intersections and hamiltonicity in almost clawfree graphs. Discrete Math. 243(2002)171-185.
[41] O. Favaron, E. Flandrin, Hao Li, Z. Ryjacek, Shortest walks in almost claw-free graphs. Ats Combin. 42(1996)223-232.
[42] Rao Li, R. H. Schellp, Hamiltonicity of (K_(1,4), K_(1,4)＋e)-free graphs. Discrete Math. 245(2002)195-202.
[43] 尤海燕，含有某些禁用子图的图的相关路问题，山东师范大学硕士毕业论文，2003．
[44] 王江鲁，爪心独立图的可扩圈，系统工程理论与实践，9(1997)68-70．
[45] 王江鲁，爪心独立图的圈可扩性，山东师范大学学报(自然科学版)，3(1997)245-247．
[46] 滕延燕，尤海燕，连通、几乎局部连通的拟无爪图是完全圈可扩的，山东师范大学学报(自然科学版)，4(2002)5-8．
[47] 蔺厚元，(K_1，4；2)—图的哈密顿性，山东师范大学硕士毕业论文，2005．
[48] Rao Li, R. H. Schelpb, Every3-connected distance claw-free graph is Hamilton-connected. Discrete Mathematics. 268(2003)185-197.
[49] Roman Cada, Evelyne Flandrin, Hao Li, Zdenek Ryjaceka, Cycles through given vertices and closures. Discrete Mathematics 276(2004) 65-80
[48] Rao Li, R. H. Schelpb, Every3-connected distance claw-free graph is Hamiltonconnected. Discrete Mathematics. 268(2003) 185-197.
[2] L. Clark, Hamiltonian properties of connected locally connected graphs. Congr. Numer. 32(1981)199-204.
[3] C. Q. Zhang, Cycles of given length in some K_(1,3)-free graphs. Discrete Math, 78(1989)307-313.
[4] A. Ainouche, H. J. Broerama, H. J. Veldman, Remarks on hamiltonian properties of claw-free graphs. Ars Combinatoria 29C(1990)110-121.
[5] 刘春房，王江鲁．[s，t]-图及其Hamilton性[J]．山东师范大学学报(自然科学版)，2005，20(1)7-8．
[6] 蔺厚元，孔淑霞．3-连通[5，3]-图的Hamilton性[J]．内蒙古师范大学学报：自然科学汉文版，2005，34(3)：288-289
[7] 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.
[8] G. R. T. Hendry, Extending cycles in graphs, Discrete Math. [J]. 85(1990)59-72.
[9] S. Brandt, G. Chen, R. Faudree, R. J. Gould and L. Lesniak: Degree conditions for 2factors, J. Graph Theory, 24 (1997) 165-173.
[10] K. Corradi and A. Hajnal: On the maximal number of independent circuits in graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423-439.
[11] P. Justesen: On independent circuits in finite graphs and a conjecture of Erdos and Posa, Annals of Discrete Math., 41 (1989) 299-306.
[12] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica, 18 (1988) 487-492.
[13] J.-C. Bermond, C.Thomassen, Cycles in digraphs - a survey. J. Graph Theory 5(1981)1-43.
[14] R. J. Gould, Updating the hamiltonian problem - a survey. J. Graph Theory 15(1991)121-157.
[15] J. A. Bondy, Basic graph theory - paths and cycles. Handbook of combinatorics, Vol. I, pp. 5-110, Amsterdam: Elsevier 1995.
[16] R. J. Gould, Advances on the hamiltonian problem - a survey. Graphs and Combin. 19(2003)7-52.
[17] L. W. Beineke, Derived graphs and digraphs. Beitrage zur Graphentheorie (Teubner, Leipzig, 1968).
[18] L. W. Beineke, Characterizations of derived graphs. J. Combin. Theory Ser. B 9(1970)129-135.
[19] D. P. Sumner, J. I. Moore, Domination perfect graphs. Notices Amer. Math. Soc. 26(1979)A-569.
[20] Mingchu Li, Hamiltonian connected claw-free graphs. Graphs and Combin. 20(2004)341-362.
[21] C. Thomassen, Reflections on graph theory. J. Graph Theory 10(1986)309-324.
[22] S. Goodman, S. Hedetniemi, Sufficient conditions for a graph to be hamiltonian. J. Combin. Theory Ser. B 16(1974)175-180.
[23] D. Duffus, M. S. Jacobson, R. J. Gould, Forbidden subgraphs and the hamiltonian theme, in: The Theory and Applications of Graphs(Kalamazoo, Mich. 1980, Wiley, New York, 1981)297-316.
[24] J. F. Maurras, Polytopes a sommets dans {0, 1}. These de Doctorat d'Etat, Universite Paris 7.
[25] S. Olariu, The strong perfect graph conjecture for pan-free graphs. J. Combin. Theory Set. B 47(1989)187-191.
[26] L. Nebesky, On the existence of 1-factors in partial squares of graphs. Czechoslovak Math. J. 29(1979)349-352.
[27] M. Sekanina, On an ordering of the set of vertices of a connected graph. Spisy Prirod. Fak. Univ. Brno (1960)137-141.
[28] S. Poljak, A note on stable sets and coloring of graphs. Comment. Math. Univ. Carolin. 15(1974)307-309.
[29] Zdenek Ryjacek, On a closure concept in claw-free graphs. J. Combin. Theory Ser. B. 70(1997)217-224.
[30] Stephan Brandt, Odile Favaron, Zdenek Ryjacek, Closure and stable hamiltonian properties in claw-free graphs. J. Graph Theory 34(2000)30-41.
[31] Bela Bolloas, Zdenek Ryjaek, Closure and hamiltonian-connectivity of claw-free graphs. Discrete Math. 195(1999)67-80.
[32] Hajo Broersma, Zdenek Ryjacek, Ingo Schiermeyer, Closure concepts: a survey. Graphs and Combin. 16(2000) 17-48.
[33] Alexander Kilmans, On graph closures. Discrete Math. 271(2003)141-168.
[34] R. Faudree, E. Flandrin, Z. Ryjacek, Claw-free graphs-a survey. Discrete Math. 164(1997)87-147.
[35] Rao Li, Hamiltonicity of 2-connected quasi claw-free graphs. Discrete Math. 283(2004)145-150.
[36] Rao Li, Hamiltoncity of 3-connected quasi claw-free graphs. Discrete Math. 265(2003)393-399.
[37] Chuanping Chen, Amel Harkat-Benhamdine, Hao Li, Distance-dominating cycles in quasi claw-free graphs. Graphs and Combin. 15(1999)279-285.
[38] Z. Ryjacek, Almost claw-free graphs. J. Graph Theory 18(1994)469-477.
[39] Mingchu Li, Longgest cycles in almost claw-free graphs. Graphs and combin. 16(2000)177-198.
[40] Mingquan zhan, Neighborhood intersections and hamiltonicity in almost clawfree graphs. Discrete Math. 243(2002)171-185.
[41] O. Favaron, E. Flandrin, Hao Li, Z. Ryjacek, Shortest walks in almost claw-free graphs. Ats Combin. 42(1996)223-232.
[42] Rao Li, R. H. Schellp, Hamiltonicity of (K_(1,4), K_(1,4)＋e)-free graphs. Discrete Math. 245(2002)195-202.
[43] 尤海燕，含有某些禁用子图的图的相关路问题，山东师范大学硕士毕业论文，2003．
[44] 王江鲁，爪心独立图的可扩圈，系统工程理论与实践，9(1997)68-70．
[45] 王江鲁，爪心独立图的圈可扩性，山东师范大学学报(自然科学版)，3(1997)245-247．
[46] 滕延燕，尤海燕，连通、几乎局部连通的拟无爪图是完全圈可扩的，山东师范大学学报(自然科学版)，4(2002)5-8．
[47] 蔺厚元，(K_1，4；2)—图的哈密顿性，山东师范大学硕士毕业论文，2005．
[48] Rao Li, R. H. Schelpb, Every3-connected distance claw-free graph is Hamilton-connected. Discrete Mathematics. 268(2003)185-197.
[49] Roman Cada, Evelyne Flandrin, Hao Li, Zdenek Ryjaceka, Cycles through given vertices and closures. Discrete Mathematics 276(2004) 65-80
[48] Rao Li, R. H. Schelpb, Every3-connected distance claw-free graph is Hamiltonconnected. Discrete Mathematics. 268(2003) 185-197.