Phylogeny numbers for graphs with two triangles (Q1570836): Difference between revisions

Let \(D\) be an acyclic directed graph (digraph) with vertex set \(V.\) Its phylogeny graph \(P(D)\) is an undirected graph on the same vertex set \(V\) where two vertices are adjecent if they are adjecent (in some order) in \(D\) or they have a common (outgoing) neighbour. The first result in this paper states that if \(G\) is an undirected graph then one can find an acyclic digraph \(D\) on a bigger underlying set, such that \(G\) is a subgraph of the phylogenetic graph of \(D\) where no arc is directed to \(G\) from outside of \(G.\) The directed graph \(D\) is called a phylogenetic digraph of \(G.\) The phylogenetic number of \(G\) is the possible minimal number of the ``extra'' vertices. These notions are similar to the widely studied notions of competiton graphs and competition numbers, introduced in ecological applications independently by Cohen and Roberts. This paper determines the phylogenetic numbers of undirected graphs with exactly two triangles.