特殊图类中子图的度和与路圈性质

来源 :山东师范大学 | 被引量 : 3次 | 上传用户:yczhudong
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在图论中,我们研究的一个十分重要而且非常活跃的课题为图的路和圈的问题,而实际生活中的很多问题都可以归结为图的路和圈问题.图论中的Hamilton问题本质上也是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一方面作了大量的研究工作.这方面的研究成果和进展可参见文献[31]-[35].其中度条件、邻域和条件以及邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,Dominating圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.由于图的Hamilton问题是一个疑难问题,所以在一般图中研究Hamilton问题会更加困难,于是人们转而研究不含有某些禁用子图的图类,如无爪图.继Beineke1970年发表的关于线图性质的文章[29]-[30]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[13]-[28]另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等.本文主要对图的度条件(任意两个不相邻子图的度和)与路圈性质(包括Hamilton连通,可迹性及Hamilron圈等)之间的关系进行了一些探索,得出了一般图及无爪图的路圈性质的几个充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了一般图及无爪图在不同度条件下的路圈性质,得到下面的结果:定理2.1.3设G是n阶2-连通图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2的度和d(H1)+d(H2)≥n—2,则G有Dominating圈.推论2.1.4设G是n阶2-连通图,如果对G中任意一个同构于K2的子图H,有d(H)≥n-2/2,则G有Dominating圈.定理2.2.4设G是n阶2-连通无爪图,如果G中任意两个分别同构于P3与K2(2阶完全图)的不相邻子图H1,H2满足d(H1)+d(H2)≥n—2,则G有Hamilton圈.定理2.3.1设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3(3阶完全图)与K1的不相邻子图H1,H2满足d(H1)+(d(H2)≥n—3,则G有Hamilton圈.在第三章中,讨论了无爪图在度条件下的Hamilton连通性质,得到下面的结果:定理3.5设G是n阶3-连通无爪图,如果G中任意两个分别同构于P3与K1的不相邻子图H1,H2满足d(H1)+d(H2)≥n,则G是Hamilton连通的.在第四章中,讨论了半无爪图在度条件下的可迹性,得到下面的结果:定理4.4设图G是n阶2-连通半无爪图,如果G中任意两个同构于K3和K1的不相邻导出子图H1,H2的度之和d(H1)+d(H2)≥n—1,则G是可迹的.
其他文献
设a(n)表示所有的非同构Abel群的个数.熟知对每一个素数p,自然数α≥1有a(pα)=P(α),这里P(α)表示α的无约束划分的个数.特别我们有a(1)=1,a(p)=1,a(p2)=2,a(p3)=3, a(p4)=5,a(p5)=7,a(p6)=11,a(p7)=15.(1)有关有限Abel群的个数函数a(n)的均值,许多数论家做了深入的研究.P.Erdos and G.Szekeres[
随着经济的高速发展,我国面临很多改革方面的问题。我国工业园区在发展初期,基本都是借鉴国外工业园区的发展模式、经验路径,结合当地实际情况,制定因地制宜的工业园区运营模式,并随着发展阶段的不同进行及时调整。本文通过对日本筑波、英国剑桥、印度班加罗尔、中关村科技园区、苏州工业园区、山东宁阳县工业园区、通辽经济技术开发区的运营模式进行对比分析,总结出适合我国工业园区发展的路径。
1919年,以青年学生为主体的五四运动的爆发,标志着青年开始登上政治舞台,作为政治意义的青年内涵开始生成。由于青年人最少保守,最能接受新鲜事物,也最朝气蓬勃,因此五四运动的爆发,不仅标志着完整意义的青年概念得以生成,而且标志着青年人成为现代文明建构中最先觉醒的群众性群体。五四运动后,湖南、湖北、浙江、安徽、四川等地,
期刊
对于董监高赔偿责任的构成要件、赔偿范围、责任免除和承担等方面司法实践的分析表明,我国法院对于董监高赔偿责任规则有不同理解,类案不同判的现象较为突出。公司法相关规则应该从以下方面予以完善:一是把董监高违反忠实义务和勤勉义务作为承担赔偿责任的行为要件;二是区分违反忠实义务和勤勉义务,前者适用严格责任原则,后者适用重大过失的归责标准;三是违反忠实义务的损失范围应该包括被告以及其关联人所得收益;四是董监高
江苏教育报刊总社主管、主办初中生世界编辑部编辑出版国际标准连续出版物号ISSN 1005-8826国内统一连续出版物号CN 32-1411/G4邮发代号28-382江苏省教育学会初中教育专业委员会会刊江苏期刊方阵双十佳期刊江苏省优秀期刊华东地区优秀期刊全国中小学图书馆馆配期
期刊