Document Type

Article

Language

eng

Format of Original

4 p.

Publication Date

1-28-2011

Publisher

Elsevier

Source Publication

Discrete Applied Mathematics

Source ISSN

0166-218X

Original Item ID

doi: 10.1016/j.dam.2010.10.008

Abstract

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-step competition graph. In this paper, we offer another generalization of the competition graph. We define the (1,2)-step competition graph of a digraph D, denoted C1,2(D), as the graph on V(D) where {x,y}∈E(C1,2(D)) if and only if there exists a vertex zx,y, such that either dDy(x,z)=1 and dDx(y,z)≤2 or dDx(y,z)=1 and dDy(x,z)≤2. In this paper, we characterize the (1,2)-step competition graphs of tournaments and extend our results to the (i,k)-step competition graph of a tournament.

Comments

Accepted version. Discrete Applied Mathematics,Vol. 159, No. 2-3 (January 28, 2011): 100-103. DOI. © Elsevier 2011. Used with permission.

Share

COinS