For
k ≥ 2 and a finite simple undirected graph
G = (
V,
E), a tree
T is a
k-leaf root of
G if
V is the set of leaves of
T and, for any two distinct
x,
y ∈
V,
xy ∈
E if and only if the distance between
x and
y in
T is at most
k.
G is a
k-leaf power if
G has a
k-leaf root. Motivated by the search for underlying phylogenetic trees, the concept of
k-leaf power was introduced and studied by Nishimura, Ragde and Thilikos and analysed further in many subsequent papers. It
is easy to see that for all
k ≥ 2, every
k-leaf power is a (
k + 2)-leaf power. However, it was unknown whether every
k-leaf power is a (
k + 1)-leaf power. Recently, Fellows, Meister, Rosamond, Sritharan and Telle settled this question by giving an example of
a 4-leaf power which is not a 5-leaf power. Motivated by this result, we analyse the inclusion-comparability of
k-leaf power classes and show that, for all
k ≥ 4, the
k- and (
k + 1)-leaf power classes are incomparable. We also characterise those graphs which are simultaneously 4- and 5-leaf powers.
In the forthcoming full version of this paper, we will show that for all k ≥ 6 and odd l with 3 ≤ l ≤ k − 3, the k- and (k + l)-leaf power classes are incomparable. This settles all remaining cases and thus gives the complete inclusion-comparability
of k-leaf power classes.
Keywords
k-leaf powers - intersection of leaf power classes - comparability of leaf power classes