Structure and Linear-Time Recognition of 4-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 a k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O(n(3))-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.