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(n(3)) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Huffner, and Niederineier 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. (c) 2006 Elsevier B.V. All rights reserved.
3-leaf powers 3-leaf roots leaf powers leaf room linear time recognition algorithm graph algorithms