Leaf Powers and Their Properties: Using the Trees

A graph

G

on

n

vertices is a

k

-

leaf power

(

$G \in {\cal G}_{k}$

) if it is isomorphic to a graph that can be “generated” from a tree

T

that has

n

leaves, by taking the leaves to represent vertices of

G

, and making two vertices adjacent if and only if they are at distance at most

k

in

T

. We address two questions in this paper:

(1) As

k

increases, do we always have

${\cal G}_{k} \subseteq {\cal G}_{k+1}$

? Answering an open question of Andreas Brandstädt and Van Bang Le [2,3,1], we show that the answer, perhaps surprisingly, is “no.”

(2) How should one design algorithms to determine, for

k

-leaf powers, if they have some property?

One way this can be done is to use the fact that

k

-leaf powers have bounded cliquewidth. This fact, plus the FPT cliquewidth approximation algorithm of Oum and Seymour [14], combined with the results of Courcelle, Makowsky and Rotics [7], allows us to conclude that properties expressible in a general logic formalism, can be decided in FPT time for

k

-leaf powers, parameterizing by

k

. This is wildly inefficient. We explore a different approach, under the assumption that a generating tree is given with the graph. We show that one can use the tree

directly

to decide the property, by means of a finite-state tree automaton. (A more general theorem has been independently obtained by Blumensath and Courcelle [5].)

We place our results in a general context of “tree-definable” graph classes, of which

k

-leaf powers are one particular example.