View Related Documents

Abstract

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

Fulltext Preview

Image of the first page of the fulltext document