重子图条件下图的Hamilton性及相关问题

来源 :西北工业大学 | 被引量 : 0次 | 上传用户:homemoons
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果一个图中含有Hamilton圈,即经过图中所有顶点的圈,那么这个图被称为是Hamilton的.本论文研究了图的Hamilton性的一类充分条件——重子图条件,推广了 Bedrossian和Faudree等人关于图的Hamilton性的禁止子图条件的结论.本论文的研究基于如下的问题:我们已知在图中禁止了某些子图结构时,能够保证所给的图是Hamilton的.如果我们允许这些子图结构存在,那么在这种子图结构上限制什么样的条件,能够仍然保证所给的图含有Hamilton圈?设G是一个图.对于给定的图H,如果G不含同构于H导出子图,那么我们说G是无H的(或H是G的禁止子图).1991年Bedrossian在其博士论文中刻画了这样的连通图对{R,S}:使得任何2-连通无R无S图是Hamilton的.设P是关于G的导出子图的某种性质.如果G中每个同构于H的导出子图G"都满足P,那么我们说G满足P(H).显然,如果G是无H的,那么G自然满足P(H).本论文研究的主要问题是:对于什么样的子图R和什么样的子图性质P,一个图G满足P(R)可以保证G是Hamilton的.我们称这种类型的充分条件为重子图条件.因此重子图条件有两个要素,即子图R和附加于子图的限制条件P.本论文对于所考虑的几类限制条件,完整刻画了能够保证任意2-连通图是Hamilton的所有子图.这些结论推广了 Bedrossian等人关于禁止子图条件的结果.此外,本文还讨论了有关图的Hamilton性的一些相关性质,包括图的最长圈经过大度顶点的性质和图中2-因子的存在性.在第一章,我们介绍了一些基本概念和本文所研究的问题的背景,并且列出了本论文得到的结论.从第二章到第六章,我们给出了某些类型的重子图条件.我们研究了所给条件下能够保证图的Hamilton性的子图.对于给定的图H,我们称图G是H-o-重的,如果图G的每一个同构于H的导出子图都含有两个不相邻的顶点度和至少为n(n是图G的阶).为研究无爪图和爪-o-重图的Hamilton性,Ryjacek和Cada分别提出了无爪图的闭包理论和爪-o-重图的闭包理论.在第二章我们介绍了闭包理论,这是本论文的一个重要工具.Ryjacek在2002年刻画了无爪图的闭包的结构.基于Ryjacek的刻画,我们刻画了爪-o-重图的闭包的结构.第三章考虑了无爪图的子图端点度条件.对于给定的图H,如果图G的每一个同构于H的子图的每个端点的度至少为(n+ k)3,那么我们称G满足Φ(H,k).Broersma在1993年提出一个猜想:任意2-连通无爪图若满足Φ(N,-2)则是Hamilton的.在第三章,我们刻画了所有这样的连通图R:使得任意2-连通无爪图若满足Φ(R,3)则是Hamilton的.我们的结论部分证明了Broersma的猜想.第四章考虑了爪-o-重图的c-重子图条件.对于给定的图H,如果G的每一个同构于H的导出子图G′和G″的每个极大团G″-C的每个非平凡分支都有一个顶点的度至少为n/2,那么我们称G是H-c-重的.我们完整刻画了使得任意2-连通爪-o-重R-c-重图是Hamilton的所有连通图R.第五章考虑了爪-o-重图的p-重子图条件.对于给定的连通图H,如果G的每一个同构于H的导出子图仅有一个中心且度至少为n/2,或存在两个中心度和至少为n,那么我们称G是H-p-重的.我们刻画了使得任意2-连通爪-o-重R-p-重图是Hamilton的所有连通图R.图G被称为是1-坚韧的,如果对任意顶点割S,G-S的分支数不超过|S|.显然所有Hamilton图都是1-坚韧的.在第六章我们考虑了 1-坚韧图的Hamilton性的禁止子图条件.我们几乎找到了所有的图R:使得任何阶至少为3的1-坚韧无R图是Hamilton的.在本论文的第七章和第八章,我们考虑了禁止子图条件和重子图条件下有关图的Hamilton性的一些相关性质.第七章研究了图的最长圈经过大度顶点的性质.对于给定的常数α ≤ 1,我们考虑对于什么样的子图R,一个2-连通图G是无R的可以保证G的任意最长圈都经过所有度至少为αn+ O(1)的顶点.我们完整刻画了满足这种性质的连通子图R.一个图的2-正则生成子图称为这个图的2-因子.Faudree等在2008年刻画了所有这样的连通图对{R,S}:使得任意2-连通无R无S图含有2-因子.在第八章我们讨论了图中2-因子的存在性的-o-重子图对条件.我们完全刻画了所有这样的子图对{R,S}:使得任意2-连通R-o-重S-o-重图含有2-因子.最后一章对本论文的工作做了一个简要总结,并提出了一些有待进一步考虑的问题.
其他文献
美索不达米亚地区主要包括巴士拉、巴格达、摩苏尔三个省份,自16世纪起为奥斯曼帝国所统治。但随着17世纪以来奥斯曼帝国不断衰弱,“东方问题”由此产生。西方列强借此机会纷纷插手其事务,都希望能最大限度地攫取奥斯曼帝国的领土与利益。20世纪初,英德两国围绕巴格达铁路问题在美索不达米亚地区展开了博弈。虽然英国在铁路问题上未能如愿以偿,但通过对美索不达米亚地区其他领域利益的掌控,彰显了其在该地区实现霸权的决
学位
女性是中国历史发展和社会变革的重要组成部分和推动力量,其拥有属于自身的独立意识和价值观念。灾荒作为一个不可抵抗的外部作用力,以粗暴、直接的方式破坏了女性原有的生存环境和家庭结构。女性在用自身力量应对灾荒的同时,灾荒也间接推动了女性解放和权力意识的发展。纵观以往研究,对于女性在灾荒中的心理变化以及女性从赈灾活动中萌生的参政意识等还有待进一步深入探讨。本文以女性视角为切入点,讨论晚清时期山西灾荒背景下
能源危机和环境污染是当今人类社会面临的全球性难题,减少二氧化碳(CO2)和其他温室气体的排放,实现碳中和是当务之急。以“能量的提供–储存–消耗–再提供”为目标的“人工生态循环”系统可以通过消耗CO2获取物质和能源并实现循环利用,有助于缓解上述问题。气凝胶材料具有超高孔隙率、超大比表面积和超低密度等特性,其连续三维网络结构不仅能够提供丰富的电荷转移通道,而且可以作为载体来掺杂或负载各种有机或无机活性
区域创新在我国现代化建设全局中占据核心地位,对区域创新绩效行政学影响因素的研究,是顺应我国创新驱动发展战略和提升地方政府核心竞争力的本质要求。已有的研究证实,区域创新生态系统有利于提升区域创新绩效,而且经济学家也证实了官员特征与经济增长和发展之间的相关关系。基于此,本文从本专业的角度出发,对行政生态、官员特征和区域创新绩效三者之间的关系展开经验研究。在文献回顾的基础上,本文构建出“行政生态-官员特
1855年,为帮助妇女就业,基督教信徒、慈善家金纳德夫人(Lady Kinnaird)在伦敦创办女青年会。因顺应社会发展,短时间内女青年会便发展到德、法、美等国。1894年,英、美、挪威、瑞典四国建立世界基督教女青年会,组织协调各国会务。1890年,美国驻华大使司徒雷登(1946-1949年任职)的母亲司徒玛丽在杭州弘道女中建立中国第一个女青年会。1923年,女青年会在杭州举办第一次基督教女青年会
黎巴嫩真主党是一个成立于1982年的什叶派伊斯兰武装组织,自成立以来,真主党不仅在它的起源地黎巴嫩开展活动,还以军事手段对抗美国及其代理人以色列在黎巴嫩南部的入侵,同时也积极在全球范围内建立活动网络,其中较引人注目的是在拉丁美洲的活动。真主党利用1975年以来的中东移民浪潮,实现了在拉丁美洲的战略渗透,该组织通过意识形态的宣传,招募和培训大量新成员,从而建立了一个以当地黎巴嫩侨民和什叶派社区为中心
动物是古典园林中的重要元素,常以景色描写出现在园林文学之中。从先秦到唐代,各种类型的园林都有着很大的变化,无论是园林形制,园林构造或是园林文化。在唐代,各种艺术类型在充分发扬本民族传统之时,还积极吸收各种文化的长处,融会贯通,最后孕育出璀璨的时代文化。园林亦是如此,皇家园林、私家园林、寺观园林都迅速发展了起来,诗人们也留下了大量的诗歌。动物的书写也是园林诗中关键的一部分,所以本文将分为三个章节对园
实现国家治理体系现代化和推进国家治理能力现代化过程中社会组织有其使命与责任,如何定位和发挥社会组织的功能是时代命题,在众多社会组织中,台商投资企业协会组织是在中国大陆各地投资、生活的台商企业及台湾同胞自愿、自发、自主形成的以维护成员利益为目标的社会组织,自1990年第一家地方台商投资企业协会——北京台商协会诞生以来,各地台商投资企业协会陆续成立,台商投资企业协会随着在内地投资生活的台商数量增多而不
什叶派在印度次大陆有着悠久的历史。7世纪,什叶派伊斯兰教因穆斯林避难、行商、战争等原因传播到了印度次大陆西北部。自德干地区的什叶派王国兴起后,什叶派政治影响扩大。在英国殖民统治时期,什叶派和逊尼派冲突表面化。19世纪后期以来,大多数什叶派知识分子向西方学习,推动了穆斯林的政治觉醒。20世纪初期,全印度什叶派会议和穆斯林联盟合作,为建立独立国家而努力。1937年以来,随着穆盟力量的增强,真纳开始偏向