学位论文 > 优秀研究生学位论文题录展示

若干特殊图类的路圈问题

作　者: 王文彬
导　师: 王江鲁
学　校: 山东师范大学
专　业: 应用数学
关键词: [s,t]-图强[s,t]-图可迹性路因子 walk 最长路 Hamilton
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

路和圈是图的两种基本结构,是分析和刻画图的有力工具,有大量的实际问题可以归结为图的路和圈问题,所以这方面一直是图论中的热点研究领域.关于路和圈的进展,已经取得了长足的发展,这方面的研究成果和进展可参见文献[15]-[18].事实上,图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton-路(可迹性),最长路,Hamilton连通,泛连通,路可扩等等；圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类.继Beinekel968,1970年发表的关于线图性质的两篇文章[19]-[20]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[30]-[47].另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图,(K1,4;2)-图,DCT图等.关于图中的路因子问题也是人们热衷的一个问题,一些成果可参考[9]-[14].关于k-walk方面的问题和研究进展可以参见文献[21]-[26].2005年,刘春房在[2]中定义了一种新的图类-[s,t]-图,即任意s个点之间至少含有t条边,这类图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用.2007年,程建民在[48]中,在[s,t]-图概念的基础上,又提出了强[s,t]-图的概念,即任意s个点之间至少含有t条独立边.本文就是研究[s,t]-图和强[s,t]-图的路圈性质.在第一章中,我们主要介绍了本文的研究背景以及已有的一些结果,以及文章中所涉及的一些概念和术语符号.在第二章中,研究了δ≥k+1的k连通[s,t]-图的可迹性,得到下面的结果：定理2.7若G为δ≥k+1的k连通[k+4,3]-图,则G有Hamilton路或G同构于(?)k+3 V Gk+1,其中Gk+1是k+1个点的任意图.推论2.8若G为δ≥k+1的k连通[k+4,3]-图且|G|≥2k+5,则G有Hamilton路.在第三章中,研究了连通[5,2]-图的最长路和连通[5,3]-图的最小2-walk,证明了下面的结果：定理3.1.5设G是n(n≥6)阶的连通[5,2]-图,则存在正整数t(t≤[n/3]),使得G的最长路的长度至少为n-t,且路长的界是紧的.定理3.2.5令G是一个n阶连通[5,3]-图,则有(1)G有一个2-walk.(2)对任意x∈V(G)存在一个2-walk C满足u(x,C)=1当且仅当x不是G的割点.(3)若n≥8且<N(x)>是连通的,则存在一个最小2-walk C使得v(x,C)=1.在第四章中,讨论了两类特殊图类的路因子问题,得到下列结果：定理4.1.5若G是连通[4,2]-图且最小度不小于d,则G有一个路因子满足每条路的顶点数不小于d+1.定理4.2.4假定图G是连通强-[6,3]图,其顶点数目为并且满足对所有的1≤i≤k都有ai≤7.如果σ2(G)≥n+k-1,那么对G的k个不同的顶点v1,v2,…vk,存在k条点不相交的路P1,P2,…Pk,使得对所有的1≤i≤k,|V (Pi)|=ai并且只是一条vi-路.

全文目录

中文摘要  5-7
英文摘要  7-9
第一章预备知识  9-16
  1.1 研究背景及已有结果  9-13
  1.2 符号概念介绍  13-16
第二章 δ≥k+1的k连通[s,t]-图的可迹性  16-19
第三章连通[5,2]-图的最长路和连通[5,3]-图的最小2-walk  19-26
  3.1 连通[5,2]-图的最长路  19-22
  3.2 连通[5,3]-图的最小2-walk  22-26
第四章两类特殊图的路因子  26-35
  4.1 [4,2]-图的路因子  26-29
  4.2 强-[6,3]图中具有指定长度的路因子  29-35
参考文献  35-38
攻读学位期间发表的学术论文  38-39
致谢  39

若干特殊图类的路圈问题

内容摘要

全文目录

相似论文