Article ID Journal Published Year Pages File Type
420965 Discrete Applied Mathematics 2007 8 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,