竞赛图和线图中的不交圈

来源 :太原理工大学 | 被引量 : 0次 | 上传用户:X5203344
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
竞赛图和线图是两类经典的图类,而研究竞赛图和线图中不交圈是一个很重要的课题 . 本文我们首先研究了竞赛图中点不交圈的问题. Bermond和Thomassen猜想:对于任何正整数r ,最小出度至少为 2r-1的有向图包含至少r个点不交有向圈. 在2014年,Bang-Jensen,Bessy和Thomasse证明该猜想在竞赛图中成立. 随后Lichiardopol证明 2r-1- 正则竞赛图包含至少7/8r-7/3个点不交有向圈. 在这篇文章中,我们证明了Lichiardopol的结论在一般竞赛图上仍然成立. 在 2010年 ,Lichiardopol又提出猜想:最小出度至少为(q-1)r-1的竞赛图包含至少r个点不交q-圈,这里q≥3,r≥1 .在本文中,我们证明当r=2时,Lichiardopol猜想成立.  其次,我们还研究了线图的哈密尔顿性及其边不交哈密尔顿圈数目问题.哈密尔顿问题是图论中的经典问题,但众所周知哈密尔顿圈的存在性问题是一个NP-完全问题. 对于任一整数s≥0 ,如果图G中任何点子集S C V (G),满足 |S|≤s且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的. 在这篇文章中,我们证明原图是平面图的4-连通线图是哈密尔顿连通的和 2-哈密尔顿的.该结果推广了 赖虫工建教授在[Every 4-connected line graph of a planar graph is ham il- tonian,Graph and Combinatorics 10 (1994) 249-253]中的结果. Bermond 猜想:如果一个图是哈密尔顿可分的那么它的线图也是哈密尔顿可分的. 现在围绕这一猜想已有许多结果,在文中我们给出了该猜想的部分结果.众所周知,如果一个图G 包含一个生成闭迹,则线图L (G )是哈密尔顿的. 最近,李浩教授等人证明了如果最小度至少为4k且至少有k个边不交生成闭迹的图G ,其线图L (G )包含k个边不交哈密尔顿圈. 在文中,我们证明如果最小度至少为4k且至少有k个边不交哈密尔顿圈的图G ,其线图L (G )包含至少2k;个边不交哈密尔顿圈.
其他文献
Internet的高速发展和多媒体技术日益广泛的应用给路由算法提出了更多的挑战和越来越高的要求。各类应用程序需要不同的QoS保证,但各QoS目标往往是相关联或相矛盾的,增加了路由
本文以左对称代数理论为基础学习了李代数上的仿凯勒结构。李代数上的仿凯勒结构对应着李群上的仿凯勒结构。关于它有两种平行的解释,其一是李代数上的一个仿凯勒结构和一个弱
期刊
近几年来,武汉市新洲一中党委坚持以邓小平理论和“三个代表”重要思想为指导,全面贯彻党的教育方针,以科学发展观统领学校教育改革发展全局,不断加强学校干部队伍建设,有效
关于游程有各种定义,一般而言,在一个有限取值的序列中,满足一定条件的同一符号的一个连串称之为一个“游程”。一个游程中同一符号出现的次数称之为游程的长度。例如,在贝努利试
随着改革不断深入,农民工数量越来越多,流动范围越来越大,充分发挥信息化管理效率高、信息量大、操作简便等优势,探索解决农民工群体党建工作的新情况、新问题,成为推动农民
本文利用半序的方法,研究了一类非线性算子方程N=A(x,x)在Banach空间上的耦合拟解的存在性,并得到了几个新的存在性定理.主要结果如下: 在定理3.1中,讨论了算子方程N=A(x,x)在B
我们用Qn(Fq)表示特征为2的有限域Fq上全体n(≥2)元二次型的集合。在Qn(Fq)上定义关系(x,y)∈Ri()二次型x-y的类型为i, 这里x,y∈Qn(Fq),i=0,1,2+,2-,3,4+,….由此所定义的关系确定
目的:分析血清同型半胱氨酸(Hcy)、甲硫氨酸(Met)和半胱氨酸(Cys)与慢性心力衰竭(CHF)的相关性及诊断价值。方法:连续纳入2018年10月至2019年9月大连大学附属中山医院178例CHF急性加