Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328423 | Discrete Applied Mathematics | 2005 | 10 Pages |
Abstract
Let D be an acyclic digraph. The competition graph of D has the same set of vertices as D and an edge between vertices u and v if and only if there is a vertex x in D such that (u,x) and (v,x) are arcs of D. In this paper, we show that the competition graphs of doubly partial orders are interval graphs. We also show that an interval graph together with enough isolated vertices is the competition graph of a doubly partial order. Finally, we introduce a new notion called the doubly partial order competition number of an interval graph and present some open questions.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Han Hyuk Cho, Suh-Ryung Kim,