The (1,2)-Step Competition Graph of a Tournament

Authors

Kim A. S. Factor, Marquette UniversityFollow
Sarah Merz, The University of the Pacific

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 C_1,2(D), as the graph on V(D) where {x,y}∈E(C_1,2(D)) if and only if there exists a vertex z≠x,y, such that either d_D−y(x,z)=1 and d_D−x(y,z)≤2 or d_D−x(y,z)=1 and d_D−y(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. © 2011 Elsevier. Used with permission.

Recommended Citation

Factor, Kim A. S. and Merz, Sarah, "The (1,2)-Step Competition Graph of a Tournament" (2011). Mathematics, Statistics and Computer Science Faculty Research and Publications. 52.
https://epublications.marquette.edu/mscs_fac/52