DIMACS TR: 98-49
Phylogeny Numbers for Graphs with Two Triangles
Authors: Fred S. Roberts and Li Sheng
ABSTRACT
Motivated by problems of phylogenetic tree reconstruction, we
introduce notions of phylogeny graph and phylogeny number. These
notions are analogous to and can be considered as natural
generalizations of notions of competition graph and competition number
that arise from problems of ecology. 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$, 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 to vertices
in $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 obtain results about phylogeny
number for graphs with exactly two triangles analogous to those for
competition number.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-49.ps.gz
DIMACS Home Page