DIMACS TR: 98-49

Phylogeny Numbers for Graphs with Two Triangles

Authors: Fred S. Roberts and Li Sheng


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