THE PHYLOGENY GRAPHS OF DOUBLY PARTIAL ORDERS

The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V(P(D)) := V(D) and E(P(D)) := {xy vertical bar N-D(+)(x) boolean AND N-D(+)(y) not equal empty set} boolean OR {xy vertical bar(x,y) is an element of A(D)}, where N-D(+)(x) := {v is an element of V(D)vertical bar(x,v) is an element of A(D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G, there exists an interval graph (G) over tilde such that (G) over tilde contains the graph G as an induced subgraph and that (G) over tilde is the phylogeny graph of a doubly partial order.