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,...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.展开更多
基金Supported by the National Natural Science Foundation of China(No.11571123,11671156)the Guangdong Provincial Natural Science Foundation(Grant No.2015A030313377)
文摘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.
