Structure and linear time recognition of 3-leaf powers

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n3) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Hüffner, and Niedermeier characterized 3-leaf powers as the (bull, dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to linear time recognition of these graphs.