【作者】 李敏；

【导师】 王江鲁；

【作者基本信息】 山东师范大学 ， 应用数学， 2007， 硕士

【摘要】 路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域。关于路和圈的进展，已经取得了长足的发展，这方面的研究成果和进展可参见文献[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）阶并且σ₂（G）≥3κ的[4，2]-图，则G含有κ个点不交的圈。更多还原

【Abstract】 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.更多还原