Title

(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.

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.