Characterising (k,ℓ)(k,ℓ)-leaf powers

We say that, for k≥2k≥2 and ℓ>kℓ>k, a tree TT with distance function dT(x,y)dT(x,y) is a (k,ℓ)(k,ℓ)-leaf root of a finite simple graph  G=(V,E)G=(V,E) if VV is the set of leaves of TT, for all edges xy∈Exy∈E, dT(x,y)≤kdT(x,y)≤k, and for all non-edges xy∉Exy∉E, dT(x,y)≥ℓdT(x,y)≥ℓ. A graph is a (k,ℓ)(k,ℓ)-leaf power   if it has a (k,ℓ)(k,ℓ)-leaf root. This new notion modifies the concept of kk-leaf powers (which are, in our terminology, the (k,k+1)(k,k+1)-leaf powers) introduced and studied by Nishimura, Ragde and Thilikos; kk-leaf powers are motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on kk-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. Many problems, however, remain open.We give the structural characterisations of (k,ℓ)(k,ℓ)-leaf powers, for some kk and ℓℓ, which also imply an efficient recognition of these classes, and in this way we improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs; one of our motivations for studying (k,ℓ)(k,ℓ)-leaf powers is the fact that strictly chordal graphs are precisely the (4,6)(4,6)-leaf powers.