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

设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时的充要条件。

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

设D是一个有向图,若存在无向图G满足:(1)G的顶点集与D的顶点集相同;(2)任取D中的两个顶点x,y,其在G中相邻当且仅当存在D中顶点z,使得D中包含一条从x到z的长为m的有向途径和一条从y到z的长为m的有向途径,则称G为D的m步竞争图,记为G=C^(m)(D).2004年,Cho和Kim首次提出竞争指数的概念.若对于某个正整数r和所有非负整数i,存在最小正整数q,使得C^(q+i)(D)=C^(q+i+r)(D),则称整数q为D的竞争指数,记为cindex(D).2008年,Kim给出了竞赛图的竞争指数的上界.2009年,Akelbek和Kirkland给出了本原有向图的竞争指数.文中研究并计算了正则多部竞赛图的竞争指数.