Phylogeny numbers (Q1270783)

For an acyclic digraph \(D=(V,A)\), the phylogeny graph \(P(D)=(V,E)\) has, for vertices \(x\neq y\), an (undirected) edge \(xy\in E\) iff (1) \((x,y)\in A\) or (2) \((y,x)\in A\) or (3) (both) \((x,a),(y,a)\in A\) for some vertex \(a\in V\); it is a supergraph of the competition graph of \(D\) for which only condition (3) is required. An acyclic digraph \(D\) is a phylogeny digraph for an undirected graph \(G\) if \(G\) is an induced subgraph of \(P(D)\), and \(D\) has no arcs from vertices outside of \(G\) to vertices in \(G\). The phylogeny number \(p(G)\) is the smallest \(r\) such that \(G\) has a phylogeny digraph \(D\) with \(| V(D)| -| V(G)| =r\). The authors show that the computation of \(p(G)\) is NP-complete (analogous to results of the first author [Food webs, competition graphs, and the boxicity of ecological phase space, Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 477-490 (1978; Zbl 0389.90036)] for competition graphs), and calculate the phylogeny number for triangulated graphs, line graphs, and graphs with 0 or 1 triangle.