扩张竞赛图中的泛连通性点对

研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件：证明了（a）设D1,D2,…,D1是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若Di（i=1,2,…,f）有1一路一圈因子,则D中必存在泛连通性点对。午且找到泛连通性点对的时间复杂度为0（n^0.5）．（b）设D是由连通但非强连通竞赛图r的强分支t（1y（t）1≥3）平衡扩张而成的,（当Iy（t）I=1时,Ti不变）,则D中必存在泛连通性点对。     

圆可分解的局部竞赛图中的点外弧泛圈问题

Yao Tianxing(Discrete Appl．Math．，2000，99：245-249)已经证明了每一个强连通竞赛图都包含点，它的每条外弧都是泛圈的．将此结论推广到强连通的圆可分解的严格局部竞赛图，并证明了每一个强连通的圆可分解的严格局部竞赛图D，它的圆分解是D=R[D1，D2，…，Da]，其中Di，i=1，2，…，a是强连通竞赛图，那么D包含一个点v，它的每条外弧是(g 1)-泛圈的，g=max{l(Ca)|Ca是包含a的最长诱导圈，a∈V(R)，l(Ca)是Ca的长度}。     

特定竞赛图中的最长圈问题

若有向图T满足条件:uv(≠)A(T)使得dT (u) dr-(v)≥k,则称图T满足O(k)条件.讨论了有向图及特殊有向图的最长圈,并且给出了某些特殊竞赛图的Hamilton圈的存在条件.     

2-强连通竞赛图外弧泛圈点的研究

郭巧萍等人证明了每个2-强连通竞赛图至少包含了3个外弧泛圈点.文章在增加一些前提条件的情况下,将对2-强连通竞赛图作进一步的研究.     

竞赛图中的最长圈问题

若有向图T满足条件:uv■A(T)使得d T(u) dT-(v)≥k,则称图T满足O(k)条件.在该文中,笔者讨论了竞赛图的最长圈,并且给出了某些有向图的Hamilton圈的存在条件.     

两点度数和条件下泛连通性的研讨

让d(u)表示点u在图G中的度数,本文对两点度数和条件图的泛连通性的性质结构做了一些研究.     

二部竞赛图中的最长圈问题

若有向图T满足条件:uv (∈)A(T)且存在一点w使得uw ∈A(T),wv∈A(T)则d-(u)+d+(v)≥n,称图T满足G(n)条件.在本文中,我们讨论了如果T(p,q)二部竞赛图满足G(n)条件且强连通,则T(p,q)包含一条长至少为2min{n+1,p,q}的圈,除非n为偶数且T(p,q)同构于一类图族B(k1,k2,k3,n/2),k1≥n/2,i=1,2,3,及特殊竞赛图的最长圈问题.     

多部竞赛图的点泛圈性

把c-部完全图的每条边任意加上一个方向后得到的定向图称为c-部竞赛图,设T为c-部竞赛图,定义ig(T)=maxx,y∈VCT│d^ (x)-d^-(y)│。给出了c－部竞赛图具有点泛圈性的一个充分条件,即：设T为c－部竞赛图（c≥13),V1,V2,…Vc为T的各分部。如果│V1│≤│V2│≤…≤│Vc│≤│V1│ 1并且ig(T)≤1,那么T具有点泛圈性。     

竞赛图中的有向哈密顿路

对于竞赛图中必有有向哈密顿路这一命题,在分析已有证明的基础上,给出了一种新的证明。     

正则竞赛图的有向生成三角形

2008年N.Lichiardopol在离散数学-竞赛图中经过给定0,1,2个公共顶点的圈.一文中提出以下公开问题:阶为2n+1的正则竞赛图T,对于任意的x∈V(T)是否存在n个有向三角形Ti使得V(Ti)∩V(Tj)=x(1≤i≤j≤n).文章证明了对于阶数为5,7,9的正则竞赛图,该问题答案是肯定的.     

竞赛图的零因子半群

讨论了竞赛图的零因子半群.一个半群S的零因子图是一个有向图Γ(S),其顶点是S中非零的零因子,S中两个不同的元x,y有一条有向边x→y当且仅当xy=0.该文证明了如果S是一个没有非零幂零元的有限半群且图Γ(S)的顶点数大于1,那么图Γ(S)不是一个竞赛图.另外对于任意的正整数n,该文完全决定了顶点数为n蹬任一个竞赛图的所有零因子半群.     

竞赛图中的完美对集

Lichiardopol在离散数学-竞赛图中经过给定的0,1,2个公共顶点的圈一文中提出以下两个公开问题;对于阶为2n+1的正则竞赛图T,(a)对任意的一个顶点w,是否存在n个有向三角形Ti生成T,且使得V(Ti)∩V(Tj)=w(1≤i相似文献   

均匀多部竞赛图的分量共轭圈问题

GUO Yubao和Volkmann证明了一个2-强连通多部竞赛图包含两个分量共轭圈,使得每部至少有一个点在其中的一个圈中.得到的结论是Guo和Volkmann的定理的进一步推广.