局部几乎正则多部竞赛图中的外路

有向图中一点u（一条弧uv）的一条外路指的是从u（uv）开始的一条有向路,如果u控制路的终点当且仅当终点也控制u.一个n-部竞赛图是n-部完全图的一个定向.令V1,V2,…,Vn是n-部有向图D的部集.如果D中存在2条外路P和P使得对于每一个i∈{1,2,…,n}都有Vi∩（V（P）∪V（P））≠Ф,则称P和P是D的一对分量共轭外路.定义D的局部非正则度为il（D）=max｜d＋（x）-d-（x）｜,x∈V（D）,其中d＋（x）和d-（x）分别表示点x的出度和入度.如果il（D）≤1,则D是局部几乎正则的.本文证明了每一个部集具有相等的基数的局部几乎正则多部竞赛图都包含2条长至少为2的分量共轭外路.     

几乎正则的n-部竞赛图的若干性质

设D是一个有向图,D中所有可能的两点x与y(x与y可以相同)的出度与 入度之差的绝对值的最大值叫做有向图D的非正则性,并记为i(D)。如果i(D)= 0,则称D为正则图;如果i(D)=1,则称D为几乎正则图。本文给出了几乎正则的n -部竞赛图的若干性质。     

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1　设G是2连通的(k,k 1)图,并且k≥V(G)3 13,如果G是偶数阶的图,则G是Hamilton图.定理2　设G是(k,k 2)图,并且k≥n3 103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.     

一类完全多部图的Hamiton性刻画

Gutin证明了在强的半完全二部图中若含有一个由两个圈构成的圈因子,则图是Hamilton图。把此定理推广到无向图中就可得到这样一个结果,即含有一个由两个圈构成的圈因子的完全二部图是Hamilton图。在此基础上,对含有由两个圈构成的圈因子的完全n（n≥3）部图进行了讨论,得出了类似于二部图的结果。     

竞赛图中的最长圈问题

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

正则c-部竞赛图中过指定顶点数目的路

文章证明了c≥2的正则c-部竞赛图D,V1,V2,…,Vc是D中的部集,如果|V1|=|V2|=…=|Vc|=r≥6,那么D包含一条阶为3c的有向路.进一步,如果r≥9,那么D包含一条来自每一部集至少两个顶点且阶为4c的有向路.更进一步,如果r≥3(n-1),这里n∈N+而且n≥3,那么D中包含一条来自每一部集至少两个顶点且阶为nc的有向路.     

多部竞赛图的点泛圈性

把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具有点泛圈性。     

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

研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图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中必存在泛连通性点对。     

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

若有向图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,及特殊竞赛图的最长圈问题.     

关于一类图的Hamilton路计数问题

研究了有向图的两个方面:竞赛图的Hamilton-路数的计数及有关竞赛排名的相关问题,多部或n-部竞赛图是完全n-部图的一个定向。根据Bongdy的强连通n-部竞赛图包含一个m-圈,其中m∈{3,4,…,n},Yeo的正则多部竞赛图是Hamilton图的原理,笔者在上述结论基础上,得到某些特殊的多部竞赛图的Hamilton路数的一些结论。