A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers

A graph GG is a kk-leaf power   if there is a tree TT such that the vertices of GG are the leaves of TT and two vertices are adjacent in GG if and only if their distance in TT is at most kk. In this situation TT is called a kk-leaf root   of GG. Motivated by the search for underlying phylogenetic trees, the notion of a kk-leaf power was introduced and studied by Nishimura, Ragde and Thilikos and subsequently in various other papers. While the structure of 3- and 4-leaf powers is well understood, for k≥5k≥5 the characterization of kk-leaf powers remains a challenging open problem.In the present paper, we give a forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. Our result generalizes known characterization results on 3-leaf powers since these are distance-hereditary 5-leaf powers.