(i, j) competition graphs

Kim A.S. Hefner, Kathryn F. Jones, Suh ryung Kim, J. Richard Lundgren, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)241-262
Number of pages22
JournalDiscrete Applied Mathematics
Volume32
Issue number3
DOIs
StatePublished - Aug 16 1991

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of '(i, j) competition graphs'. Together they form a unique fingerprint.

Cite this