On CCE graphs of doubly partial orders |
| |
Authors: | Seog-Jin Kim Yoomi Rho |
| |
Affiliation: | a Department of Mathematics Education, Konkuk University, Seoul 143-701, Republic of Korea b Department of Mathematics Education, Seoul National University, Seoul 151-742, Republic of Korea c Department of Mathematics, University of Incheon, Incheon 402-749, Republic of Korea |
| |
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 v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (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 C4 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: | Competition graph Competition-common enemy graph Interval graph Doubly partial order |
本文献已被 ScienceDirect 等数据库收录! |
|