摘要
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.
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)
