The phylogeny graphs of doubly partial orders

Abstract

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\mid N_D^{+}(x)\cap N_D^{+}(y)\ne \varnothing \}\cup \{xy\mid (x,y)\in A(D)\}$, where $N_D^{+}(x):=\{v\in V(D)\mid (x,v)\in 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 $\tilde{G}$ such that $\tilde{G}$ contains the graph $G$ as an induced subgraph and that $\tilde{G}$ is the phylogeny graph of a doubly partial order.

9 pages, 1 figure

References in corpus (3)

• The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C^{\prime }(p)$
• The competition hypergraphs of doubly partial orders
• The niche graphs of doubly partial orders

Cited by in corpus (5)

• The competition hypergraphs of doubly partial orders
• On the phylogeny graphs of degree-bounded digraphs
• A graph with the partial order competition dimension greater than five
• On the partial order competition dimensions of chordal graphs
• On the competition graphs of $d$-partial orders