An approach towards generating k-leaf powers for phylogenetic tree construction

---

Phylogeny is the evolutionary history of a species or group of organisms. Evolutionary trees can be analogized to graph trees, thus determination of these structures aids in inferring the evolutionary history of groups of organisms, extant and extinct. K-leaf power graphs enhance the ability of researchers to map paralogous and xenologous speciation events in what is a considerably difficult area to correctly predict past relationships.

Forbidden subgraph characterization is a method by which to characterize a graph class with a set of graphs that do not belong to that class. Identification of minimal forbidden induced subgraphs is one method of characterizing the k-leaf powers of graph trees. A tree is a k-leaf power if, and only if, the leaves are connected by at most distance k. Structures for 2-leaf, 3-leaf, and 4-leaf powers are well understood, however, there does not exist a published list of forbidden subgraph leaf powers for values of k ≥ 4. In service of cladistics, k-leaf powers are frequently edited by adding or removing nodes and edges to the closest “proper” representation of a pairwise comparison of groups of organisms.

We demonstrate a deterministic, reductionist approach to generating 4-leaf, 5-leaf, and 6-leaf powers using Python, the graph library Networkx, and the Nauty suite of graph generation and labelling programs. The list of non-k-leaf powers in this range has not been proven finite, so this approach does not cover all possible structures should the list be infinite.

---

---

---

---