The (1,2) ( 1 , 2 ) -step competition graph of a tournament
The competition graph of a digraph, introduced by Cohen in 1968, has been extensively studied. More recently, in 2000, Cho, Kim, and Nam defined the m m -step competition graph. In this paper, we offer another generalization of the competition graph. We define the (1,2) ( 1 , 2 ) -step competition graphof a digraph D D , denoted C1,2(D) C 1 , 2 ( D ) , as the graph on V(D) V ( D ) where {x,y}?E(C1,2(D)) { x , y } ? E ( C 1 , 2 ( D ) ) if and only if there exists a vertex z?x,y z ? x , y , such that either dD?y(x,z)=1 d D ? y ( x , z ) = 1 and dD?x(y,z)?2 d D ? x ( y , z ) ? 2 or dD?x(y,z)=1 d D ? x ( y , z ) = 1 and dD?y(x,z)?2 d D ? y ( x , z ) ? 2 . In this paper, we characterize the (1,2) ( 1 , 2 ) -step competition graphsof tournaments and extend our results to the (i,k) ( i , k ) -step competition graphof a tournament.
competition graph tournament digraph m m -step graph m m m m m