强竞赛图中顶点的外弧泛圈性

来源 :山西大学 | 被引量 : 4次 | 上传用户:wenwen0000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
竞赛图无疑是有向图中一类非常重要的图,并且它已经被广泛研究.关于竞赛图中有向路和有向圈问题的研究非常深入而且成果丰硕.称有向图D是泛圈的,如果它包含从3到|V(D)|的每个长度的圈.称有向图D的一个顶点(一条弧)是k泛的,如果它属于每个l-圈(k≤l≤|V(D)|).当k=3时,也称该顶点(弧)是泛圈的.称有向图D是顶点泛圈(弧泛圈)的,如果它的每个顶点(弧)是泛圈的.对某个k∈{3,4,…,|V(D)|},称有向图D是弧-k-圈的,如果D的每条弧都包含在一个长为k的圈中.显然,有向图D是弧泛圈的当且仅当对每个k=3,4,…,|V(D)|,它是弧-k-圈的.目前,在竞赛图的泛圈性、顶点泛圈性及弧泛圈性方面已有了很多结果.有向图D的一条从顶点x出发的弧被称为是x的一条外弧.如果一个顶点的所有外弧在D中都是k泛的,则称这个顶点是外弧k泛顶点.当k=3时,也称该顶点是外弧泛圈顶点.2000年,Yao,Guo和Zhang首次对竞赛图中顶点的外弧泛圈性作了讨论,证明了强竞赛图中外弧泛圈顶点的存在性.本文主要研究强竞赛图中顶点的外弧泛圈性问题.  本文共分五章.第一章介绍了有向图中的一些相关的基本概念以及论文内容的安排.  第二章回顾了竞赛图中的一些相关结果.  第三章研究了强竞赛图中外弧泛圈顶点的个数.在2000年,Yao,Guo和Zhang证明了每个强竞赛图T都包含一个外弧泛圈顶点.同时他们提出一个猜想:每个k-强竞赛图至少存在k个这样的顶点.现在已经证明了该猜想对k=1,2,3是对的.然而,由于Yeo给出的下面的例子,这个猜想对k≥4是不成立的.设T1,T2和T3都是阶至少为k的可迁竞赛图.T是在Ti之间添加弧得到的一个竞赛图,使得T1(→)T2(→)T3(→)T1.显然T是k-强的.由于Ti中的任何一条弧都不在T的一个3-圈中,所以仅有在每个Ti(i=1,2,3)中出度为零的顶点是T的外弧泛圈顶点.但是Yeo提出的下列猜想可能是正确的:每个2-强竞赛图至少包含3个外弧泛圈顶点.在3.2节,我们证明了Yeo的猜想是成立的.另外,对于最小出度为1的强竞赛图,Yao等人找到一个强竞赛图的无限类使得其中每个强竞赛图恰包含一个外弧泛圈顶点.那么我们自然要问:对于最小出度至少为2的强竞赛图包含几个外弧泛圈顶点呢?在3.3节,我们证明了连通度为1且最小出度至少是2的强竞赛图也至少包含3个外弧泛圈顶点,并举例说明了这个结果的最佳可能性.结合3.2和3.3节的这两个结论,我们得到具有最小出度至少是2的强竞赛图至少包含3个外弧泛圈顶点.  第四章研究了恰有3个外弧泛圈顶点的强竞赛图.Yeo在2005年给出一类例子说明对任意的正整数k,存在一类k-强竞赛图,使得其中每个竞赛图至多包含3个外弧泛圈顶点.那么除了这类例子以外,是否k-强竞赛图就包含k外弧泛圈顶点?本章中,我们给出了恰有3个外弧泛圈顶点的5-强竞赛图的一个必要条件,证明了恰有3个外弧泛圈顶点的5-强竞赛图是某一类图中的成员.设T1,T2和T3都是阶为k≥5的强竞赛图,满足u,v1和w1分别是T1,T2和T3中出度为零的顶点,且有(V(T1)-{u})→u,(V(T2)-{v1})→v1及(V(T3)-{w1})→w1.设T4是一个竞赛图.令T0是在Ti(i=1,2,3,4)之间添加弧得到的所有强竞赛图的集合,使得T1(→)T2(→)T3(→)T1且T4中的每个顶点都控制{u,v1,w1},其它的弧任意定向.设T是一个恰包含3个外弧泛圈顶点的5-强竞赛图,则T是T0中的一个成员.我们的结果表明,除T0以外,5-强竞赛图一定包含4个外弧泛圈顶点.  第五章讨论了k-强竞赛图中外弧5泛顶点的数目.Feng等人在2006年证明了k-强竞赛图(k≥3)至少包含k+1个外弧4泛顶点,我们证明了k-强竞赛图(k≥4)至少包含k+2个外弧5泛顶点.
其他文献
河南清丰县王什乡原党委书记刘相义,在一年半的时间里,采取变卖农业开发物资、造假虚报水利工程款等方法,获得非法资金230余万元。其中,吃喝近70万元,贪污3万余元。清丰县人
该论文介绍了这套油田产能设备设计绘图专业软件的理论基础、运行环境、主要开发等.这套软件以目前Autodesk公司的最新版本AutoCAD R14 for Windows为基础进行开发,增加了下
本论文主要是研究耦合长短波方程的多辛算法,耦合的长短波方程是Schrodinger-Kdv方程组的特殊形式,本文构造了Euler-box格式、多辛Preissman格式和Fourier拟谱格式求解耦合长短
该文先导出了未知参数的似然方程,给出了未知参数的显式的近似极大似然估计和近似区间估计.与通常Type-Ⅱ截尾情形相比,多重Type-Ⅱ截尾更具有普遍性和实用性,然而其在数学自
该文阐述了三维高精度储层参数反系统的原理和结构,该系统利用测井资料和地震资料作为输入,应用正反演迭代算法,首先建立井点波阻抗模型,并以此作为种子点,然后,在层位地质模
该文主要讨论了酉群U(1,n;C)上的Jorgensen不等式的建立及其应用.在第一章中,讨论了酉变换的一些基本性质.在第二章中,得到了一个关于复合元素的类型类别的重要引理,应用此引
该文首先从边缘检测谈起,比较经典的边缘检测方法诸如Sobel边缘检测方法、Prewitt边缘检测方法、Robert边缘检测方法、LoG边缘检测方法以及Canny边缘检测方法;分析了它们的相
该论文描述了三维地质模型的基本工作流程和模型所需要的输入数学项及用于地质分析的输出图件,概述了三维地质模型的框架体系.根据该文提出的丛聚误差方程组给出了Kriging减
该文主要利用E.L.Wachspress和罗钟铉提出的楔函数及广义楔函数的方法讨论了曲边三角元上光滑插值格式的构造及某些具体曲边元上的光滑曲面的显式表示.该文共分四章,第一章介
论文共分五章.前四章介绍了小波分析的基础理论,第五章是应用部分,用小波方法给出了线性常微分方程近似解的统一表达式.小波分析是近几年迅速发展起来的一种强有力的数学工具