论文部分内容阅读
竞赛图和线图是两类经典的图类,而研究竞赛图和线图中不交圈是一个很重要的课题 . 本文我们首先研究了竞赛图中点不交圈的问题. 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;个边不交哈密尔顿圈.