论文部分内容阅读
在图论中,有关哈密尔顿分解和泛弧的问题一直是图论学者们研究的重点.随着Bang-Jensen在1990年提出局部半完全有向图的概念,局部半完全有向图中的哈密尔顿分解和泛弧的问题也开始受到研究工作者的广泛关注. 没有2-圈的局部半完全有向图是局部竞赛图.2012年,Bang-Jensen和Huang(J Combin Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图包含两个弧不相交的强连通生成子图当且仅当图D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图包含两个弧不相交的哈密尔顿国的猜想.本文主要研究局部半完全有向图中弧不相交的哈密尔顿路和哈密尔顿圈.2016年,Bai等人(Discrete Mathematics.2016,339:2063-2065)研究了竞赛图中的泛弧问题,本文研究了局部半完全有向图的子类——圆有向图中的泛弧问题,并将竞赛图中的结论推广到了圆有向图中. 针对这些问题,本文共分为五章. 第一章,介绍了有向图的基本概念,以及问题的研究背景. 圆有向图作为局部半完全有向图的一个重要的子类,一直是人们研究局部半完全有向图中各种问题的起点.第二章,讨论了圆有向图中的弧不相交的哈密尔顿路和哈密尔顿圈,证明了: (a)2-强的圆有向图中包含弧不相交的哈密尔顿路和哈密尔顿圈当且仅当它不是偶圈的二次幂; (b)任意3-强的圆有向图中必包含两个弧不相交的哈密尔顿圈; (c)任意4-强的圆有向图中必包含一个哈密尔顿圈和两个哈密尔顿路,使得它们两两弧不相交; (d)将这些结论推广到正圆有向图中. 第三章,研究了圆可分解的局部半完全有向图中弧不相交的哈密尔顿路和圈,证明了任意3-强的圆可分解的局部半完全有向图中包含两个弧不相交的哈密尔顿圈,从而说明了Bang-Jensen和Huang的猜想对圆可分解的局部竞赛图成立.并刻画了包含弧不相交的哈密尔顿路和哈密尔顿国的2-强的圆可分解的局部竞赛图. 第四章,研究了非圆可分解的局部竞赛图中弧不相交的哈密尔顿路和圈,证明了任意2-强的非圆可分解的局部竞赛图中包含两个起点和终点分别不同的弧不相交的哈密尔顿路.并结合圆可分解的局部竞赛图的结论,将Thomassen的关于竞赛图的结论(任意2-强的竞赛图包含两条弧不相交且起点和终点互不相同的哈密尔顿路)推广到局部竞赛图上. 第五章,设uv是有向图D中的一条弧,如果D中任意顶点和弧uv都包含在某个公共圈中,则称弧uv是D的一条泛弧.本章证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图,并给出了判断是否一个圆有向图的每条弧都是泛弧的多项式时间算法.