正则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。

多部竞赛图中包含在一些圈中的顶点

一个c-部竞赛图是一个完全c-部图的定向,在本文中我们证明了强联通c-部竞赛图的每个顶点都属于顶点恰好取自m个部集的圈C^m,其中m∈{3,4,…,c},且这些圈满足V(C^3)V(C^4)…V(C^c)。