Rooted directed path graphs are leaf powers (Q965972)

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph \(G=(V,E)\) is called \(k\)-leaf power if it admits a \(k\)-leaf root, i.e., a tree \(T\) with leaves \(V\) such that \(uv\) is an edge in \(G\) if and only if the distance between \(u\) and \(v\) in \(T\) is at most \(k\). Moroever, a graph is simply called leaf power if it is a \(k\)-leaf power for some natural number \(k\). This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a \(k\)-leaf power. The authors show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, they provide the largest currently known proper subclass of leaf powers, i.e., the class of rooted directed path graphs. Subsequently, they study the leaf rank problem, the algorithmic challenge of determining the minimum \(k\) for which a given graph is a \(k\)-leaf power. Firstly, they give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, they use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, they provide efficient algorithms to compute \(2|V|\)-leaf roots for given ptolemaic or (unit) interval graphs \(G = (V,E)\).