Summary: We say that, for \(k\geq 2\) and \(\ell > k\), a tree \(T\) with distance function \(d_T(x,y)\) is a \((k,\ell )\)-leaf root of a finite simple graph \(G=(V,E)\) if \(V\) is the set of leaves of \(T\), for all edges \(xy \in E\), \(d_T(x,y)\leq k\), and for all non-edges \(xy \notin E\), \(d_T(x,y)\geq \ell \). A graph is a \((k,\ell )\)-leaf power if it has a \((k,\ell )\)-leaf root.
This new notion modifies the concept of \(k\)-leaf powers (which are, in our terminology, the \((k,k+1)\)-leaf powers) introduced and studied by Nishimura, Ragde and Thilikos; \(k\)-leaf powers are motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on \(k\)-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,\ell )\)-leaf powers, for some \(k\) and \(\ell \), 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,\ell )\)-leaf powers is the fact that strictly chordal graphs are precisely the (4,6)-leaf powers.