(i, j) Competition Graphs
Format of Original
Discrete Applied Mathematics
Original Item ID
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.
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.