Generalized Competition Index of Primitive Digraphs

作     者：Li-hua YOU Fang CHEN Jian SHEN Bo ZHOU 

作者机构：School of Mathematical Sciences South China Normal University Department of Mathematics Texas State University 

出 版 物：《Acta Mathematicae Applicatae Sinica》 (应用数学学报（英文版）)

年 卷 期：2017年第33卷第2期

页      面：475-484页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Supported by the National Natural Science Foundation of China(No.11571123,11671156) the Guangdong Provincial Natural Science Foundation(Grant No.2015A030313377) 

主　　题：competition index m-competition index scrambling index primitive digraph 

摘      要：For any positive integers k and m, the k-step m-competition graph C^（D） of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices vi, v2, .., Vm in D such that there are directed walks of length k from x to vi and from y to vi for all 1 ≤ i≤ m. The m-competition index of a primitive digraph D is the smallest positive integer k such that Ckm（D） is a complete graph. In this paper, we obtained some sharp upper bounds for the m-competition indices of various classes of primitive digraphs.