Towards a Characterization of Leaf Powers by Clique Arrangements

In this paper, we use the new notion of clique arrangements to suggest that leaf powers are a natural special case of strongly chordal graphs. The clique arrangement

${{\cal A}}(G)$

of a chordal graph

G

is a directed graph that represents the intersections between maximal cliques of

G

by nodes and the mutual inclusion of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without bad

k

-cycles for

k

 ≥ 3.

The class

${{\cal L}}_k$

of

k

-leaf powers consists of graphs

G

 = (

V

,

E

) that have a

k

-leaf root, that is, a tree

T

with leaf set

V

, where

xy

 ∈ 

E

if and only if the

T

-distance between

x

and

y

is at most

k

. Structure and linear time recognition algorithms have been found for 2-, 3-, 4-, and, to some extent, 5-leaf powers, and it is known that the union of all

k

-leaf powers, that is, the graph class

${{\cal L}} = \bigcup_{k=2}^\infty {{\cal L}}_k$

, forms a proper subclass of strongly chordal graphs. Despite that, no essential progress has been made lately.

In this paper, we characterize the subclass of strongly chordal graphs that have a clique arrangement without certain bad 2-cycles and show that

${{\cal L}}$

is contained in that class.