竞赛图和线图是两类经典的图类,而研究竞赛图和线图中不交圈是一个很重要的课题.本文我们首先研究了竞赛图中点不交圈的问题.Bermond和Thomassen 猜想:对于任何正整数r,最小出度至少为2r-1的有向图包含至少r个点不交有向圈.在2014年,Bang-Jensen,Bessy和Thomasse证明该猜想在竞赛图中成立.随后Lichiardopol证明2r-1-正则竞赛图包含至少7/6r-7/3个点不交有向圈.在这篇文章中,我们证明了Lichiardopol的结论在一般竞赛图上仍然成立.在2010年,Lichiardopol又提出猜想:最小出度至少为(q-1)r-1的竞赛图包含至少r个点不交q-圈,这里q ≥ 3,r ≥ 1.在本文中,我们证明当r = 2时,Lichiardopol猜想成立.其次,我们还研究了线图的哈密尔顿性及其边不交哈密尔顿圈数目问题.哈密尔顿问题是图论中的经典问题,但众所周知哈密尔顿圈的存在性问题是一个NP-完全问题.对于任一整数s ≥ 0,如果图G中任何点子集S(?)V(G)满足|S|≤3且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的.在这篇文章中,我们证明原图是平面图的4-连通线图是哈密尔顿连通的和2-哈密尔顿的.该结果推广了赖虹建教授在[Every 4-connected line graph of a planar graph is hamil-tonian,Graph and Combinatorics 10(1994)249-253]中的结果.Bermond 猜想:如果一个图是哈密尔顿可分的那么它的线图也是哈密尔顿可分的.现在围绕这一猜想已有许多结果,在文中我们给出了该猜想的部分结果.众所周知,如果一个图G包含一个生成闭迹,则线图L(G)是哈密尔顿的.最近,李浩教授等人证明了如果最小度至少为4k且至少有k个边不交生成闭迹的图G,其线图L(G)包含k个边不交哈密尔顿圈.在文中,我们证明如果最小度至少为4k且至少有k个边不交哈密尔顿圈的图G,其线图L(G)包含至少2k个边不交哈密尔顿圈.
暂无评论