DIMACS TR: 98-50
Extremal Phylogeny Numbers
Authors: Fred S. Roberts and Li Sheng
ABSTRACT
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