DIMACS TR: 98-50

Extremal Phylogeny Numbers

Authors: Fred S. Roberts and Li Sheng


Given an acyclic digraph $D=(V,A)$, define its {\em phylogeny graph} $G=P(D)$ by taking the same vertex set as $D$ and, for $x\neq y$ in $V$, letting $xy\in E(G)$ if and only if $(x,y)\in A$ or $(y,x)\in A$ or $(x,a), (y,a) \in A$ for some vertex $a\in V$. Given a graph $G=(V,E)$, we shall call the acyclic digraph $D$ a {\em phylogeny digraph} for $G$ if $G$ is an induced subgraph of $P(D)$ and $D$ has no arcs from vertices outside of $G$ to $G$. The {\em phylogeny number} $p(G)$ is defined to be the smallest $r$ such that $G$ has a phylogeny digraph $D$ with $|V(D)|-|V(G)|=r$. In this paper, we apply the famous theorem of Tur\'an to show that for graph $G$ with $n$ vertices, $p(G)\le \lfloor\frac{n^2}{4}\rfloor -n+1$ and that $p(G)$ achieves this upper bound if and only if $n\le 3$ or $G=K(\lfloor\frac{n}{2}\rfloor, \lceil\frac{n}{2}\rceil)$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-50.ps.gz
DIMACS Home Page