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

来源：应用数学学报杂志2021年第3期北京时间：

作者：张新鸿, 郭燕, 李瑞娟, 张越

单位：1 太原科技大学应用科学学院, 太原 030024;<br>2 山西大学数学科学学院, 太原 030006

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

关键词：正则多部竞赛图,m步竞争图,竞争指数,竞争周期