(i, j) Competition Graphs
Document Type
Article
Language
eng
Format of Original
22 p.
Publication Date
8-1991
Publisher
Elsevier
Source Publication
Discrete Applied Mathematics
Source ISSN
0166-218X
Original Item ID
doi: 10.1016/0166-218X(91)90002-E
Abstract
If D is an acyclic digraph, its competition graph has the same vertex set as D and an edge between vertices x and y if and only if for some vertex u, there are arcs (x, u) and (y, u) in D. We study competition graphs of acyclic digraphs D when the indegrees and outdegrees of the vertices of D are restricted. Under degree restrictions, we characterize the competition graphs and are able to solve the important open problem of characterizing acyclic digraphs whose competition graphs are interval graphs. We also characterize the competition graphs which are interval graphs.
Recommended Citation
Factor, Kim A. S.; Jones, Kathryn F.; Kim, Suh-ryung; Lundgren, J.Richard; and Roberts, Fred S., "(i, j) Competition Graphs" (1991). Mathematics, Statistics and Computer Science Faculty Research and Publications. 373.
https://epublications.marquette.edu/mscs_fac/373
Comments
Discrete Applied Mathematics, Vol. 32, No. 3 (August 1991): 241-262. DOI.
Kim Factor was affiliated with the University of Colorado Denver at the time of publication. Kim Factor published under the name Hefner at the time of publication.