Generalized competition index of a primitive digraph

AbstractFor positive integers k and m, and a digraph D, the k-step m-competition graph Cmk(D) of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v1,v2,…,vm in D such that there are directed walks of length k from x to vi and from y to vi for 1⩽i⩽m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that Cmk(D) is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph