类竞赛图

来源 :山西大学 | 被引量 : 0次 | 上传用户:timeman
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个有向图是半完全的,如果它的任意两个不同的顶点之间至少有一条弧.没有2圈的半完全有向图是竞赛图.竞赛图无疑是有向图中一类非常重要的图,它已经被广泛研究.1990年Bang-Jensen首次引进了竞赛图的一类推广图-局部半完全有向图.对有向图D中任一顶点x,如果它的内邻集和外邻集诱导的子图都是半完全有向图,则称D是局部半完全有向图.1993年Bang-Jensen引进了弧局部半完全有向图.对有向图D中任意两个相邻的顶点x,y,如果x的内邻和y的内邻是相邻的或者是同一个顶点,且x的外邻和y的外邻是相邻的或者是同一个顶点,则称有向图D是弧局部半完全有向图.1995年Bang-Jensen和Huang引进了准传递有向图.2004年Bang-Jensen引进了3准传递有向图.2011年,Hernández-Cruz引进了k准传递有向图.对有向图D中任意一条长为k的路,若起点和终点是相邻的,则称有向图D是k准传递有向图.当k=2时,k准传递有向图也称为准传递有向图.这几类有向图显然都是竞赛图的推广图,即这些有向图中包含竞赛图作为子图.有关这些图类的研究已逐渐发展成为一个较成熟的研究领域.在本文中,我们称竞赛图的推广图为类竞赛图,并就类竞赛图中的若干问题进行了研究.  本文共分四章.第一章介绍了无向图和有向图中的一些基本概念以及论文内容的安排.  第二章研究了竞赛图和局部半完全有向图中的王.2.1节介绍了类竞赛图中关于王的一些研究成果.2.2节研究了强连通的竞赛图中的k王(k≥3),并且证明了强连通的竞赛图中至少有k+1个k王,并给出正好有k+1个k王时竞赛图的结构.已经知道每一个竞赛图中至少有一个2王.每一个没有内度为零的顶点的竞赛图中至少有3个2王.2.2节还给出了正好有3个2王的竞赛图的结构.  在2.3节,我们研究了局部半完全有向图中的k王,并且证明了,对局部半完全有向图D,下面几条成立:  (a)假设D不是强连通的且D1,D2,…,Dr是D的半完全分解.若r=2,则D包含一个2王;若r≥3,则D包含一个r-1王;  (b)假设D是一个强连通的、圆可分解的局部半完全有向图,圆分解为D=R[S1,S2,…,Sp].则D包含一个g(R)王,其中g(R)是R的围长;  (c)假设D是一个强连通的、非圆可分解的局部半完全有向图.则D包含一个2王.  第三章研究了弧局部内半完全有向图.在2004年,Bang-Jensen刻画了强连通的弧局部半完全有向图的结构,并证明了弧局部半完全有向图D中有哈密顿圈当且仅当D是强连通的且有圈因子.有向图H1,H2,H3,H4的定义在第一章可以找到.Bang-Jensen定义不包含H1和H2作为子图的有向图为弧局部半完全有向图.在本文中,我们定义不包含H1作为子图的有向图为弧局部内半完全有向图;不包含H2作为子图的有向图为弧局部外半完全有向图;不包含H3作为子图的有向图为弧准传递有向图;不包含H4作为子图的有向图为3反路-准传递有向图.Galeana-Sánchez定义不包含H3作为子图的有向图为3准传递有向图.本文使用了3准传递有向图这个概念.  Bang-Jensen猜想:一个弧局部内半完全有向图D中有哈密顿圈当且仅当D是强连通的且有圈因子.在3.1节,我们介绍了弧局部半完全有向图的一些研究结果.在3.2节,我们刻画了强连通的弧局部内半完全有向图的结构并由此证明了Bang-Jensen的猜想是正确的.  Laborde,Payan和Xuong提出了下面的猜想:每一个有向图中都存在一个独立集与每一条最长的路是相交的.在3.3节,我们给出了不强连通的弧局部内半完全有向图的性质,并由此证明对弧局部内半完全有向图这个猜想是正确的.  第四章研究了k准传递有向图.在4.1节,我们介绍了k(准)传递有向图的一些研究成果.若有向图D中任意一条长为k路,(起点和终点是相邻的)起点控制终点,则称有向图D是k(准)传递有向图.在4.2节,给出了不强连通的3准传递有向图的性质.在4.3节,使用4.2节的结果证明了对3准传递有向图上一章Laborde,Payan和Xuong提出的猜想是正确的.  Hernández-Cruz猜想:无向图G可定向为3准传递有向图当且仅当它可以定向为3传递有向图.在4.4节,我们证明这个猜想是正确的.  在4.5节,我们研究了3准传递有向图中的k王,并且证明3准传递有向图中存在4王.  Hernández-Cruz猜想:设k-1是一个质数,D是一个阶至少为k+1的强连通k传递有向图.若D中包含一条长为n的有向圈,并且D不是对称的k+1圈,其中n≥k,(n,k-1)=1,则D是一个完全有向图.在4.6节,我们证明这个猜想是正确的.
其他文献
该文将S看成纯八元数空间ImO中的单位球面.利用八元数的有关Cayley三角的性质,给出ImO的一组基,再利用这组基计算出S中Kahler角为常数的非复曲面的结构方程.最后我们根据G群
随着中国教育制度的不断改革,无论是教育目的还是方式方法,都是为了让学生拥有更加合理且有效的学习方法.相比初中数学而言,初中数学不再是单单运用公式去解决问题,更多的在
全文共分三章.第一章是关于动力系统的局部分支与混沌的预备知识,简要地介绍连续动力系统和离散动力系统的各种局部分支理论,同时对混沌的一些定义、特征以及通向混沌的道路
耦合函数在对随机变量联合分布的分析中发挥着重要的作用,该文利用耦合函数的方法讨论风险之间的相关性对VaR的影响.对VaR的次可加性进行了分析,给出了推广的正态分布族的次
该论文主要研究线性弹性振动系统的自适应镇定及参数估计.全文分为六章.第二章考虑一维弦振动方程在其一端固定,另一端具有不确定振幅的调和干扰及控制输入情形下的边界镇定
我国南海是内波的多发区域,吕宋海峡被认为是南海北部大振幅内孤立波的发生源。内孤立波振幅大,流速高,促进海水内部物质和能量的输运。同时它产生的剪切流和湍流给全球能量的运输和耗散作了重要贡献,并且对海上工程,海洋生物,军事等都有重要影响。因此,海洋内波研究对海上生产和海洋工程具有重要意义。本文使用了MITgcm模式对吕宋海峡海域进行了非静力条件下的三维模拟,较为准确的模拟了内孤立波的生成和传播过程,并
学位
活跃于商场和官场,他在嵊州曾经“风光一时”在绍兴嵊州,吴肖根的名字可谓无人不知。此次吴肖根的“落马”在当地不亚于一场地震。吴肖根在嵊州的不寻常地位,缘于他在当地政
作文教学中,只要教师牢固树立“敢为天下新”的创新理念,持之以恒,创新不辍,作文教学的创新之花定能结出丰硕的果实.
在这篇文章中,我们首先刻画了A,D型的箭图Q的单表示的通过任一个表示的generic扩张以及任一个表示的通过单表示的generic扩张.这有助于我们更好地理解映射 和量子群的单项式
Finsler流形是无二次型限制的黎曼流形,它是具有Finsler度量的光滑流形.而(α,β)度量是一类重要的Finsler度量,常见的类型有(α+β)/α,α+β.该文构造了具有特殊曲率性质的