We say that, for
k ≥ 2 and ℓ>
k, a tree
T is a (
k,ℓ)
-leaf root of a graph G = (
V
G
,
E
G
) if
V
G
is the set of leaves of
T, for all edges
xy ∈
E
G
, the distance
d
T
(
x,
y) in
T is at most
k and, for all non-edges
xy Ï EGxy \not\in E_G
,
d
T
(
x,
y) is at least ℓ. A graph
G is a (
k,ℓ)
-leaf power if it has a (
k,ℓ)-leaf root. This new notion modifies the concept of
k-leaf power which was introduced and studied by Nishimura, Ragde and Thilikos 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. For
k = 3 and
k = 4, structural characterisations and linear time recognition algorithms of
k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger
k, the recognition problem is open.
We give structural characterisations of (k,ℓ)-leaf powers, for some k and ℓ, which also imply an efficient recognition of these classes, and in this way we also improve and extend a recent paper
by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers.
Keywords (k and ℓ) -leaf powers - leaf powers - leaf roots - strictly chordal graphs - linear time algorithms