Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420965 | Discrete Applied Mathematics | 2007 | 8 Pages |
Abstract
Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and vv if and only if there are vertices ww and x in D such that (w,u)(w,u), (w,v)(w,v), (u,x)(u,x), and (v,x)(v,x) are arcs of D . We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C4C4 as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Seog-Jin Kim, Suh-Ryung Kim, Yoomi Rho,