正则二部竞赛图的竞争指数

Competitive Index of k-regular Bipartite Tournaments

设D是一个有向图,如果存在无向图G满足V(G)=V(D),且对G中任意的顶点x,y相邻当且仅当G中包含顶点z,使得存在从x到z以及从y到z的长为m的途径,则称G为D的m步竞争图,记为C^(m)(D).若存在最小正整数q,使得C^(q+i)(D)=C^(q+i+r)(D),其中r是某个正整数,i是所有非负整数,则称q为D的竞争指数,记为cindex(D).给出了几乎正则二部竞赛图的竞争指数等于1时的充要条件,并进一步刻画了k正则二部竞赛图的竞争指数等于1和2时的充要条件。

Let D be a directed graph,if there is an undirected graph G that satisfies V(G)=V(D),and any pair of vertices x,y∈G is adjacent if and only if the vertex z is included G,there is a walk from x to z and from y to z,then it is called m-step competition graph,and is written as C^(m)(D).There is the smallest positive integer q such that C^(q+i)(D)=C^(q+i+r)(D)for some positive integer r and all nonnegative integer i.Such an integer q is called as the competition index of D and is denoted by cindex(D).An necessary and sufficient condition for the almost regular bipartite tournaments when the competition index is equal to 1 is proposed.Further,the sufficient and necessary condition for the k-regular bipartite tournaments is characterized when the competition index is equal to 1 or 2.