Leaf power (original) (raw)

In the mathematical area of graph theory, a k-leaf power of a tree T is a graph G whose vertices are the leaves of T and whose edges connect pairs of leaves whose distance in T is at most k. That is, G is an induced subgraph of the graph power , induced by the leaves of T. For a graph G constructed in this way, T is called a k-leaf root of G. A graph is a leaf power if it is a k-leaf power for some k. These graphs have applications in phylogeny, the problem of reconstructing evolutionary trees.