#  $k$-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden
Induced Subgraphs for $k\geq 5$

Max Dupré la Tour McGill University<EMAIL_ADDRESS>Manuel Lafond
Université de Sherbrooke<EMAIL_ADDRESS>Ndiamé Ndiaye McGill
University<EMAIL_ADDRESS>Adrian Vetta McGill University.
<EMAIL_ADDRESS>
###### Abstract

A graph $G=(V,E)$ is a $k$-leaf power if there is a tree $T$ whose leaves are
the vertices of $G$ with the property that a pair of leaves $u$ and $v$ induce
an edge in $G$ if and only if they are distance at most $k$ apart in $T$. For
$k\leq 4$, it is known that there exists a finite set $\mathscr{F}_{k}$ of
graphs such that the class $\mathcal{L}(k)$ of $k$-leaf power graphs is
characterized as the set of strongly chordal graphs that do not contain any
graph in $\mathscr{F}_{k}$ as an induced subgraph. We prove no such
characterization holds for $k\geq 5$. That is, for any $k\geq 5$, there is no
finite set $\mathscr{F}_{k}$ of graphs such that $\mathcal{L}(k)$ is
equivalent to the set of strongly chordal graphs that do not contain as an
induced subgraph any graph in $\mathscr{F}_{k}$.

##  1 Introduction

A fundamental question in graph theory concerns whether or not a graph
$G=(V,E)$ can be represented (or approximated) by a simpler graph, for
instance a tree $T$, while preserving the desired information from the
original graph. The pairwise distances of $G$ often need to be summarized into
sparser structures, with notable examples including _graph spanners_ [10, 1,
14, 20] and _distance emulators_ [27, 8, 28] which respectively ask for a
subgraph of $G$ or for another graph that approximates the distances of $G$.
If the distance information to preserve only concerns “close together” versus
“far apart” then this can take the following form: given a graph $G$ and an
integer $k$, does there exists a tree $T$ whose leaves are the vertices of
$G$, such that distinct vertices $u$ and $v$ are adjacent in $G$ if and only
if the distance $d_{T}(u,v)$ from $u$ to $v$ in $T$ is at most $k$? If the
answer is affirmative then $G$ is dubbed a $k$-leaf power of $T$ (and $T$ is
dubbed a $k$-leaf root of $G$).

The study of $k$-leaf powers and roots were instigated by Nishimura, Ragde and
Thilikos [25]. On the applied side, these graphs are of significant interest
in the field of computational biology with respect to phylogenetic trees,
which aim to explain the distance relationships observed on available data
between species, genes, or other types of taxa. Indeed, $k$-leaf powers can be
used to represent and explain pairs of genes that underwent a bounded number
of evolutionary events in their evolution [23, 15], or that have conserved
closely related biological functions during evolution [19]. On the theory
side, despite their simplicity, several fundamental graph theoretic problems
concerning $k$-leaf powers remain open. The purpose of this research is to
resolve one such long-standing open problem. Specifically, we prove that the
class $\mathcal{L}(k)$ of $k$-leaf power graphs cannot be characterized via a
finite set of forbidden induced subgraphs for $k\geq 5$. In contrast, for
$k\leq 4$ such finite characterizations were previously shown to exist [11, 5,
3].

###  1.1 Background

Let $\mathcal{L}(k)$ denote the class of all $k$-leaf power graphs, for $k\geq
2$. The class of all leaf power graphs is then denoted by
$\mathcal{L}=\bigcup_{k}\mathcal{L}(k)$. The literature on leaf power graphs
has primarily focused on two major themes. One, obtaining graphical
characterizations for both the class $\mathcal{L}$ and the classes
$\mathcal{L}(k)$, for fixed values of $k$. Two, designing efficient algorithms
to recognize graphs that belong to these classes.

Let’s begin with the former theme. Here important roles are played by chordal
and strongly chordal graphs. A graph is _chordal_ if every cycle of length
four or more has a _chord_ , an edge connecting two non-consecutive vertices
of cycle. A graph is _strongly chordal_ if it is chordal and all its even
cycles of length $6$ or more have an _odd chord_ , a chord connecting two
vertices an odd distance apart along the cycle. Now, it is known that every
graph in $\mathcal{L}$ and $\mathcal{L}(k)$ is _strongly chordal_.111In
particular they do not contain, as induced subgraphs, chordless cycles of
length greater than three, nor sun graphs. To see this, first note that a leaf
power graph is an induced subgraph of a power of a tree. Second, note that
trees are strongly chordal, and taking powers and induced subgraphs both
preserve this property [26]). However, the reciprocal is not true: there exist
strongly chordal graphs that are not leaf powers. The first such example was
discovered by Brandstädt et al. [4]. Subsequently, six additional examples
were identified by Nevries and Rosenke [24] who conjectured that any strongly
chordal graph not containing any of these seven graphs as an induced subgraph
is a leaf power. However, a weaker version of this conjecture, that there are
only a finite number (rather than seven) of obstructions was was disproved by
Lafond [17]. The author constructed an infinite family of _minimal_ strongly
chordal graphs that are not leaf powers (i.e., removing any vertex results in
a leaf power).

For fixed $k$, the conjecture that $\mathcal{L}(k)$ may be characterized by a
finite set of obstructions remained open. Indeed, for $k\leq 4$, the classes
$\mathcal{L}(k)$ can be characterized as chordal graphs that do not contain
any graph from $\mathscr{F}_{k}$ as induced subgraphs, where $\mathscr{F}_{k}$
is a finite set. Specifically:

  * •

$k=2$: A graph is in $\mathcal{L}(2)$ if and only if it is a disjoint union of
cliques. That is, $\mathcal{L}(2)$ is precisely the set of graphs that forbid
$P_{3}$, the chordless path with three vertices, as an induced subgraph. Thus
$|\mathscr{F}_{2}|=1$.

  * •

$k=3$: Dom et al. [11] gave the first characterization of $\mathcal{L}(3)$: a
graph is in $\mathcal{L}(3)$ if and only if it is chordal and does not contain
a bull, a dart or a gem as induced subgraph. Thus $|\mathscr{F}_{3}|=3$. Other
characterizations of $\mathcal{L}(3)$ were later discovered [5]

  * •

$k=4$: Brandstädt, Bang Le and Sritharan [3] proved that a graph is in
$\mathcal{L}(4)$ if and only if it is chordal and does not contain as induced
subgraph one of a finite set $\mathscr{F}_{4}$ of graphs222Formally, they show
that the set of basic 4-leaf power, where no two leaves of the leaf root share
a parent, can be characterized by chordal graphs which do not have one of 8
graphs as induced subgraphs. $\mathscr{F}_{4}$ can be deduced from this set..

Given this, the aforementioned conjecture naturally arose: for every $k$, is
the class $\mathcal{L}(k)$ equivalent to the set of chordal graphs that do not
contain as induced subgraphs any of a finite set $\mathscr{F}_{k}$ of graphs?

For $k=5$, Brandstädt, Bang Le and Rautenbach [6] proved this is true for a
special subclass of $\mathcal{L}(5)$. Specifically, the _distance hereditary_
333A graph $G$ is distance hereditary if for all pairs of vertices $(u,v)$ in
all subgraphs of $G$ either the distance is the same as in $G$ or there is no
path from $u$ to $v$. $5$-leaf power graphs are chordal graphs that do contain
a set of $34$ graphs as induced subgraphs. However, for the general case, they
state

> “For $k\geq 5$, no characterization of $k$-leaf powers is known despite
> considerable effort. Even the characterization of $5$-leaf powers appears to
> be a major open problem.” [6]

The contribution of this paper is to disprove the conjecture: for all $k\geq
5$, it is impossible to characterize the set of $k$-leaf powers as the set of
chordal graphs which are $\mathscr{F}_{k}$-free for $|\mathscr{F}_{k}|$
finite. In fact, we show that even for the more restrictive class of strongly
chordal graphs it is impossible to characterize the set of $k$-leaf powers as
the set of strongly chordal graphs which are $\mathscr{F}_{k}$-free for finite
$|\mathscr{F}_{k}|$.

Let us conclude this section by discussing the second major theme in this
area, namely, efficient recognition algorithms. The computational complexity
of deciding whether or not a graph is in $\mathcal{L}$ is wide open. We
remark, however, that some graphs in $\mathcal{L}$ have a leaf rank that is
exponential in the number of their vertices, where the leaf rank of a graph
$G$ is the minimum $k$ such that $G\in\mathcal{L}(k)$ [16]. The question of
computing the leaf rank of subclasses of $\mathcal{L}$ in polynomial time was
recently initiated in [21].

For fixed values of $k$, though, progress has been made in designing
polynomial-time algorithms for the $\mathcal{L}(k)$ recognition problem. For
$\mathcal{L}(2),\mathcal{L}(3)$ and $\mathcal{L}(4)$, this immediately follows
from the above characterizations because $\mathscr{F}_{2},\mathscr{F}_{3}$ and
$\mathscr{F}_{4}$ are finite. In fact, all these three recognition problems
can be solved in linear time; see [5, 3]. Using a dynamic programming
approach, Chang and Ko [9] described a linear-time algorithm for the
$\mathcal{L}(5)$ recognition problem, and Ducoffe [12] proposed a polynomial-
time algorithm for the $\mathcal{L}(6)$ recognition problem. Recently, Lafond
[18] designed a polynomial-time algorithm for the $\mathcal{L}(k)$ recognition
problem, for any constant $k\geq 2$. The algorithm is theoretically efficient
albeit completely impractical: the polynomial’s exponent depends only on $k$
but is $\Omega(k\mathbin{\uparrow}\mathbin{\uparrow}k)$, that is, a tower of
exponents $k^{k^{\cdot^{\cdot^{\cdot^{k}}}}}$ of height $k$. We remark that
the algorithm does not rely on specific characterizations of $k$-leaf power
graphs aside from the fact that they are chordal. It appears difficult to
significantly improve its running time without a better understanding of the
graph theoretical structure of graphs in $\mathcal{L}(k)$. Our work assists in
this regard by improving our knowledge of $k$-leaf powers in terms of
forbidden induced subgraphs.

###  1.2 Overview and Results

We now present an overview of the paper and our results. In Section 2 we
present our main theorem:

######  Theorem 1.1.

For $k\geq 5$, the set of $k$-leaf powers cannot be characterized as the set
of strongly chordal graphs which are $\mathscr{F}_{k}$-free, where
$\mathscr{F}_{k}$ is a finite set of graphs.

There we discuss the three types of gadgets we need. These gadgets can be
combined to form an infinite family of pairwise incomparable graphs which are
not $k$-leaf powers. We prove the main theorem modulo three critical lemmas on
the gadgets. In Section 3 we present proofs of the three critical lemmas.
Finally, in Section 4 we show how to modify our proof to derive a similar
theorem for _linear $k$-leaf powers_:

######  Theorem 1.2.

For $k\geq 5$, the set of linear $k$-leaf powers cannot be characterized as
the set of strongly chordal graphs which are $\mathscr{F}_{k}$-free where
$\mathscr{F}_{k}$ is a finite set of graphs.

Here, a linear $k$-leaf power is a graph that has a $k$-leaf root which is the
subdivision of a _caterpillar_. We remark that that the class of linear leaf
powers can be recognised in linear time, as shown by Bergougnoux et al. [2].

##  2 The Proof Modulo Three Critical Lemmas

In this section we prove our main theorem, Theorem 1.1, assuming the validity
of three critical lemmas. The proofs of these lemmas form the main technical
contribution of the paper and are deferred to Section 3.

###  2.1 Preliminaries

Before presenting the proof of Theorem 1.1, we present necessary definitions
and notations. Let’s start with a formal definition of $k$-leaf powers. Let
$G=(V,E)$ be a simple finite graph, and $k\geq 2$ be an integer. $G$ is called
a $k$-_leaf power_ if there exists a tree $T$, known as a $k$-leaf root of
$G$, with the following properties:

  * •

$V$ is the set of leaves of $T$.

  * •

For any pair of vertices $u,v\in V$, there is an edge $uv\in E$ if and only if
the $d_{T}(u,v)\leq k$.

Here $d_{T}$ is the distance metric induced by the tree $T$ when two adjacent
vertices are a distance of $1$ apart. To simplify the notation, we will use
$d$ instead of $d_{T}$ when the context is clear. We will use the notation
$\operatorname{dist}_{G}$ to denote distance within the graph $G$ and thus
distinguish it from the distance $d_{T}$ induced by a leaf root $T$.

###  2.2 The Proof of the Main Theorem

To prove Theorem 1.1, for any $k\geq 5$, we will construct a collection of
arbitrarily large strongly chordal graphs that are _minimal non_ $k$_-leaf
powers_. Specifically, these graphs have the property that any “strict”
induced subgraph is a $k$-leaf power.

To accomplish this goal, we fix $k\geq 5$. We then begin by designing a graph
$H_{n}$, for all $n\geq 0$, built using three gadget graphs joined in series.
First will be the top gadget and last the bottom gadget. In between will be
exactly $n$ copies of the interior gadget. We denote these gadget graphs by
$\text{Top},\text{Bot}$ and $I$, respectively. These gadget graphs will
satisfy a set of critical properties. To formalize these properties we require
the following definition. Given a graph $G=(V,E)$ and $T$ a $k$-leaf root of
$G$. For $v\in V$, let $m_{T}(v)=\min_{u\in V\setminus\\{v\\}}d_{T}(u,v)$.
That is, $m_{T}(v)$ is the shortest distance in the tree $T$ from the leaf $v$
to any other leaf $u$.

The aforementioned properties of $\text{Top},\text{Bot}$ and $I$ are stated in
the subsequent three critical lemmas.

######  Lemma 2.1.

For all $k\geq 4$, there exists a gadget graph Top that contains a vertex
$t\in V(\text{Top})$ such that:

  1. 1.

For any $k$-leaf root $T$ of Top, $m_{T}(t)=3$.

  2. 2.

There exists a $k$-leaf root $T_{\text{Top}}$ of Top.

######  Lemma 2.2.

For all $k\geq 4$, there exists a gadget graph Bot that contains a vertex
$b\in V(\text{Bot})$ such that:

  1. 1.

For any $k$-leaf root $T$ of Bot, $m_{T}(b)\leq k-1$.

  2. 2.

There exists a $k$-leaf root $T_{\text{Bot}}$ such that
$m_{T_{\text{Bot}}}(b)=k-1$

######  Lemma 2.3.

For all $k\geq 5$, there exists a gadget graph $I$ that contains two distinct
vertices $t_{I},b_{I}\in V(I)$ such that:

  1. 1.

For all $k$-leaf roots $T$ of $I$, $m_{T}(t_{I})\geq k\Longrightarrow
m_{T}(b_{I})=3$.

  2. 2.

There exists a $k$-leaf root $T_{I}$ of $I$ such that $m_{T_{I}}(t_{I})=k$ and
$m_{T_{I}}(b_{I})=3$.

  3. 3.

There exists a $k$-leaf root $R_{I}$ of $I$ such that $m_{R_{I}}(t_{I})=k-1$
and $m_{R_{I}}(b_{I})=4$.

We will prove the existence of gadget graphs $\text{Top},\text{Bot}$ and $I$
required to verify the three lemmas in Section 3. For the rest of the section,
we will assume these lemmas and use them to prove our main result.

Figure 1: The construction of $H_{n}$

First, as alluded to above, we then combine our three gadgets to create an
intermediary graph $H_{n}$. In particular, $H_{n}$ is the graph obtained by
connecting in series one copy of Top, then $n$ copies of $I$:
$I^{1},\dots,I^{n}$ and finally one copy of Bot. This construction is
illustrated in Figure 1. The vertices $t_{I}$ and $b_{I}$, mentioned in Lemma
2.3, of the $j$-th copy $I^{j}$ are denoted $t^{j}_{I}$ and $b^{j}_{I}$,
respectively. Notice that to connect the gadgets within $H_{n}$, we identify
the vertices described in Lemmas 2.1, 2.2, and 2.3 as follows. We identify $t$
with $t^{1}_{I}$, for all $j<n$, $b^{j}_{I}$ with $t^{j+1}_{I}$, and finally,
$b^{n}_{I}$ with $b$. As a special case when $n=0$, the graph $H_{0}$ is
obtained by taking Top and Bot and identifying $t$ with $b$.

In order to prove Theorem 1.1 we must study the structure of $H_{n}$. We
denote by $H_{n}-\text{Top}$ (resp. $H_{n}-\text{Bot}$) the graph obtained
from $H_{n}$ by deleting the top gadget Top (resp. the bottom gadget Bot),
i.e. removing all vertices of Top (resp. Bot) except for the common vertex
$t=t_{I}^{1}$ (resp. $b=b_{I}^{n}$). Of importance is the next lemma.

######  Lemma 2.4.

The graph $H_{n}$ has the following properties:

  1. 1.

$\operatorname{dist}_{H_{n}}(b,t)\geq n$.

  2. 2.

$H_{n}$ is strongly chordal.

  3. 3.

$H_{n}-\text{Top}$ and $H_{n}-\text{Bot}$ are both $k$-leaf powers.

  4. 4.

$H_{n}$ is not a $k$-leaf power.

###### Proof.

In order to prove 1, the distance between $t_{I}$ and $b_{I}$ in $I$ is at
least $1$ because the two vertices are distinct. Hence
$\operatorname{dist}_{H_{n}}(b,t)\geq n$, because there are $n$ copies of the
interior gadget $I$.

For the proof of 2, the three gadgets are $k$-leaf powers and, therefore, are
strongly chordal. The construction of $H_{n}$ does not introduce additional
cycles; thus, $H_{n}$ remains strongly chordal.

To prove 3, we combine the leaf-root properties provided by the gadgets
$T_{\text{Top}}$, $T_{\text{Bot}}$, $T_{I}$, and $R_{I}$, as illustrated in
Figure 2.

Figure 2: The $k$-leaf roots of $H_{n}-\text{Bot}$ and $H_{n}-\text{Top}$

The left tree in Figure 2 is obtained by merging $T_{\text{Top}}$ with $n$
copies of $T_{I}$, denoted as $T_{I}^{1},\dots,T_{I}^{n}$. We identify $t$
with $t_{I}^{1}$, and we identify the of $t$ in $T_{\text{Top}}$ with
$t_{I}^{1}$ and with the parent of $t_{I}^{1}$ in $T_{I}^{1}$. Similarly, for
all $j\leq n-1$, we identify $b_{I}^{j}$ and its parent with $t_{I}^{j+1}$ and
its parent, respectively. We now prove that the resulting tree is a $k$-leaf
root of $H_{n}-\text{Top}$. Top and each copy of the interior gadget $I$ are
the $k$-leaf power of the corresponding subtree: $T_{\text{Top}}$ for Top and
$T_{I}^{j}$ for the $j$-th copy of $I$. It remains to show that we do not
introduce any additional, unwanted edges. If $v_{1}$ is a leaf of
$T_{\text{Top}}$ different from $t$, and $v_{2}$ is a leaf of $T_{I}^{1}$
different from $t^{1}_{I}$ then, using Lemma 2.1, we conclude $d(v_{1},t)\geq
m_{T_{\text{Top}}}(t)=3$. Furthermore, using the second point of Lemma 2.3, we
conclude $d(v_{2},t_{I}^{1})\geq m_{T_{I}}(t_{I})=k$. Therefore,
$d(v_{1},v_{2})\geq d(v_{1},t)+d(v_{2},t_{I}^{1})-2\geq k+3-2=k+1>k$, and
there is no edge between $v_{1}$ and $v_{2}$ in the $k$-th power of the tree.
Similarly, if $v_{1}$ is a leaf of $T_{I}^{j}$ different from $b_{I}^{j}$ for
some $j\leq n-1$ and $v_{2}$ is a leaf of $T_{I}^{j+1}$ different from
$t_{I}^{j+1}$, we have $d(v_{1},b_{I}^{j})\geq 3$ and
$d(v_{2},t_{I}^{j+1})\geq k$. Thus, $d(v_{1},v_{2})\geq
d(v_{1},b_{I}^{j})+d(v_{2},t_{I}^{j+1})-2\geq k+3-2=k+1>k$, and there is no
edge between $v_{1}$ and $v_{2}$ in the $k$-th power of the tree.

The right tree in Figure 2 is formed by merging $n$ copies of $R_{I}$, denoted
$R^{1}_{I},\dots,R^{n}_{I}$, with $T_{\text{Bot}}$. For all $j\leq n-1$, we
identify $b_{I}^{j}$ with $t_{I}^{j+1}$, and we identify the parent of
$b_{I}^{j}$ with the parent of $t_{I}^{j+1}$. Finally, we identify $b_{I}^{n}$
and its parent in $R^{n}_{I}$ with $b$ and its parent in $T_{\text{Bot}}$,
respectively. Similar to the left tree, we must prove that no additional,
unwanted edges are created. If $v_{1}$ is a leaf of $R^{j}_{I}$ different from
$b_{I}^{j}$ for some $j\leq n-1$ and $v_{2}$ is a leaf of $R^{j+1}_{I}$
different from $t_{I}^{j+1}$ then, using Lemma 2.3, we conclude
$d(v_{1},b_{I}^{j})\geq m_{R_{I}}(b_{I})=4$ and $d(v_{2},t_{I}^{j+1})\geq
m_{R_{I}}(t_{I})=k-1$. Thus, $d(v_{1},v_{2})\geq
d(v_{1},b_{I}^{j})+d(v_{2},t_{I}^{j+1})-2\geq k-1+4-2=k+1>k$, and there is no
edge between $v_{1}$ and $v_{2}$ in the $k$-th power of the tree. Similarly if
$v_{1}$ is a leaf of $R^{n}_{I}$ different from $b_{I}^{n}$ and $v_{2}$ is a
leaf of $T_{\text{Bot}}$ different from $b$ then we have
$d(v_{1},b_{I}^{n})\geq 4$ and, using Lemma 2.2, $d(v_{2},b)\geq k-1$.
Therefore $d(v_{1},v_{2})\geq d(v_{1},b_{I}^{n})+d(v_{2},b)-2\geq k+1>k$ and
$v_{1}$,$v_{2}$ are not connected in the $k$-th power of the tree. This
completes the proof of 3, the third point of the lemma.

It remains to prove 4, the final point of the lemma. We start by proving by
induction that for any integer $n$, in any $k$-leaf root $T$ of
$H_{n}-\text{Bot}$, there is a leaf at distance $3$ of $b$ in $T$. When $n=0$,
there are no gadgets $I$ between Bot and Top, so $b=t$ and the property holds
by property 1 of Lemma 2.1. Turning to the induction step, assume that the
property holds for some $n\geq 0$ and consider a $k$-leaf root $T$ of
$H_{n+1}-\text{Bot}$. Since $H_{n}-\text{Bot}$ is an induced subgraph of
$H_{n+1}-\text{Bot}$, some induced subgraph of $T$ is a $k$-leaf root of
$H_{n}-\text{Bot}$. By the induction hypothesis, there exists a vertex $v_{1}$
in $H_{n}-\text{Bot}$ at a distance exactly $3$ from $b_{I}^{n}=t_{I}^{n+1}$
in an induced subgraph of $T$. Adding vertices will not alter the distance, so
$d(v_{1},b_{I}^{n})=3$ in $T$. We claim that every vertex of $I^{n+1}$ is at
distance at least $k$ from $b_{I}^{n}=t_{I}^{n+1}$ in $T$ (except $b_{I}^{n}$
itself). Assume, by contradiction, that there exists a vertex $v_{2}$ in the
last copy $I^{n+1}$, distinct from $b_{I}^{n}$ such that that
$d(v_{2},b_{I}^{n})\leq k-1$ . This assumption would imply that
$d(v_{1},v_{2})\leq d(v_{1},b_{I}^{n})+d(v_{2},b_{I}^{n})-2\leq 3+(k-1)-2=k$,
meaning that $v_{1}$ and $v_{2}$ are connected in the $k$-th power of $T$,
contradicting the fact that $T$ is a $k$-leaf root of $H_{n+1}-\text{Bot}$.
Therefore, all vertices in $I^{n+1}$, distinct from $b_{I}^{n}$, are at a
distance of at least $k$ from $b_{I}^{n}$ in $T$. We can now apply property 1
of Lemma 2.3, which concludes the induction.

Now assume by contradiction that there exists a $k$-leaf root $T$ of $H_{n}$.
$T$ induces a $k$-leaf root of $H_{n}-\text{Bot}$. In particular, there exists
a vertex $v_{1}$ in $H_{n}-\text{Bot}$ such that $d(b_{I}^{n},v_{1})=3$.
Moreover, property 1 of Lemma 2.2 implies that there exists a vertex $v_{2}$
in Bot, distinct from $b$, such that $d(v_{2},b)\leq k-1$. Combining these
equations, we get $d(v_{1},v_{2})\leq k-1+3-2=k$, contradicting the fact that
there is no edge between $v_{1}$ and $v_{2}$. This proves that $H_{n}$ is not
a $k$-leaf power, as desired. ∎

As stated $H_{n}$ is an intermediate graph in proving the main result. We will
actually show the existence of an induced subgraph $G_{k,n}$ of $H_{n}$ that
is strongly chordal and minimal non $k$-leaf power. More precisely, we have
the following lemma.

######  Lemma 2.5.

For all $k\geq 5$ and $n\geq 0$, there exists a graph $G_{k,n}$ such that:

  1. 1.

$G_{k,n}$ is strongly chordal and contains at least $n$ vertices.

  2. 2.

$G_{k,n}$ is not a $k$-leaf power.

  3. 3.

If $G\neq G_{k,n}$ is an induced subgraph of $G_{k,n}$ then $G$ is a $k$-leaf
power.

###### Proof.

Let $G_{k,n}$ be a minimal induced subgraph of $H_{n}$ that is not a $k$-leaf
power. It is strongly chordal because, by Lemma 2.4, $H_{n}$ is strongly
chordal. By definition, $G_{k,n}$ is not in $\mathcal{L}(k)$, but every
induced subgraph $G$ of $G_{k,n}$ is in $\mathcal{L}(k)$ if $G\neq G_{k,n}$.
It remains to prove that $|G_{k,n}|\geq n$. By Lemma 2.4, both
$H_{n}-\text{Bot}$ and $H_{n}-\text{Top}$ are in $\mathcal{L}(k)$. Therefore,
$G_{k,n}$ must contain a vertex from Top and a vertex from Bot. Moreover,
$G_{k,n}$ is connected by its minimality, since the disjoint union of $k$-leaf
powers is a $k$-leaf power. Hence, $G_{k,n}$ must contain a path from Top to
Bot. By Lemma 2.4, $\operatorname{dist}_{H_{n}}(b,t)\geq n$, and therefore
$|G_{k,n}|\geq n$. ∎

Our main result follows directly from Lemma 2.5

###### Proof of Theorem 1.1.

If $\mathcal{L}(k)$ is the set of strongly chordal graphs which are
$\mathscr{F}_{k}$-free, then $\mathscr{F}_{k}$ must contain $G_{k,n}$ for all
$n$ because it is strongly chordal and a minimal non $k$-leaf power by Lemma
2.5. But the set $\\{G_{k,n},n\geq 0\\}$ is infinite because $G_{k,n}$ has
more than $n$ vertices. Therefore $\mathscr{F}_{k}$ must be infinite, which
concludes the proof of Theorem 1.1. ∎

##  3 The Gadget Graphs

So we have proven the main theorem modulo the three critical lemmas. Recall to
prove these lemmas we must construct the appropriate three gadget graphs,
namely Top, Bot and $I$. We present these constructions and give formal proofs
of Lemmas 2.1, 2.2 and 2.3 in this section.

We start with a general observation. In a tree $T$, if a pair of leaves are a
distance of $2$ apart, they share the same parent. Consequently, their
distances to every other leaf are identical. A consequence of this is that if
two vertices are not connected by an edge, or if they have different
neighborhoods in a graph, they must be at a distance of at least $3$ in any
leaf root of that graph. In the gadgets we describe in this section, any two
vertices connected by an edge always have distinct neighborhoods. Therefore,
we assume that for any pair of vertices $x$ and $y$ and any leaf root $T$, we
have $d_{T}(x,y)\geq 3$.

###  3.1 The Top Gadget

We begin by showing the existence of an appropriate top gadget, Top.

See 2.1

###### Proof.

Let $P$ be the path on the $2k-3$ vertices $v_{1},\dots,v_{2k-3}$. The top
gadget Top is defined as $P^{k-2}$ with $t=v_{k-2}$. Two examples of Top are
shown in Figure 3, for the cases $k\in\\{5,6\\}$. First, note that Top is a
$k$-leaf power. In particular, a $k$-leaf root of Top is the caterpillar
$T_{\text{Top}}$, which is constructed by attaching a leaf to every vertex of
$P$. For the first property, we use Lemma $2$ from [29] which implies that in
any $k$-leaf root $T$ of Top, we have $d(v_{k-3},v_{k-2})\leq 3$. ∎

$v_{1}$$v_{2}$$t=v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

$v_{1}$$v_{2}$$v_{3}$$t=v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$

Figure 3: The Top Gadget for $k=5$ and $k=6$.

###  3.2 The Bottom Gadget

Next, we construct the bottom gadget, Bot. A key technical tool we require is
the 4-Point Condition. This is the following classical characterization of
tree metrics.

######  Theorem 3.1 (4-Point Condition).

[7] Let $d$ be a distance on a finite set $V$, then there exists a tree $T$
whose leaves are $V$ such that $\forall u,v\in V$ $d_{T}(u,v)=d(u,v)$ if and
only if the following condition is true for all $(u,v,w,t)\in V$:

$d(u,v)+d(w,t)\leq\max\left\\{d(u,w)+d(v,t),d(v,w)+d(u,t)\right\\}.$

Our bottom gadget Bot will simply be a diamond, the complete graph on 4
vertices minus one edge. Consequently, we begin by proving the following
corollary of the $4$-Point Condition when applied to a diamond.

######  Corollary 3.2.

In any $k$-leaf root $T$ of a diamond with vertex set
$\left\\{b,v_{1},v_{2},v_{3}\right\\}$ where $(v_{1},v_{3})\notin E$,
$d(b,v_{2})\neq k$.

###### Proof.

Assume for contradiction that $d(b,v_{2})=k$. Then since $d(v_{1},v_{3})>k$,
we get $d(v_{1},v_{3})+d(b,v_{2})>2k$.

On the other hand, since we have a leaf root of the diamond, we must have:

$\max\left\\{d(v_{1},v_{2}),d(v_{2},v_{3}),d(v_{3},b),d(b,v_{1})\right\\}\leq
k.$

This implies that $d(v_{1},v_{2})+d(v_{3},b)\leq 2k$ and
$d(v_{2},v_{3})+d(b,v_{1})\leq 2k$.

So,
$d(v_{1},v_{3})+d(b,v_{2})>\max\left\\{d(v_{1},v_{2})+d(v_{3},b),d(v_{2},v_{3})+d(b,v_{1})\right\\}$
which contradicts Theorem 3.1 ∎

Corollary 3.2 allows us to prove our critical lemma for the bottom gadget.

See 2.2

###### Proof.

Let the graph Bot be the diamond with vertex set $\\{b,v_{1},v_{2},v_{3}\\}$
and non-edge $(v_{1},v_{3})$. By Corollary 3.2, $d(b,v_{2})\leq k-1$ in any
leaf root. Thus the first property holds. For the second property, there are
two cases, illustrated in Figure 4, depending upon the parity of $k$.

$b$$v_{1}$$v_{2}$$v_{3}$$\frac{k-1}{2}$$\frac{k+1}{2}$$\frac{k-1}{2}$$\frac{k+1}{2}$O
(a) $T_{\text{Bot}}$ for $k$ odd

$b$$v_{1}$$v_{2}$$v_{3}$$\frac{k}{2}-1$$\frac{k}{2}$$\frac{k}{2}-1$$\frac{k}{2}$$O_{1}$$O_{2}$
(b) $T_{\text{Bot}}$ for $k$ even

Figure 4: The $k$-leaf roots of the diamond with $\min_{v\in
V(D)\setminus\\{b\\}}d(b,v)=k-1$. Here the bold edges denote paths of the
described length; the dotted edges are the edges of the diamond.

  * •

If $k$ is odd, start with $b$ and $v_{2}$ at distance $k-1$. Let $O$ be the
midpoint of the two at distance $\frac{k-1}{2}$ from both. Set $v_{1}$ and
$v_{3}$ to be each at distance $\frac{k+1}{2}$ from $O$. Then $b$ and $v_{2}$
will both be at distance exactly $k$ from both $v_{1}$ and $v_{3}$, but
$v_{1}$ and $v_{3}$ are at distance $k+1$ from each other. Thus, the only
distance which is greater than $k$ is $d(v_{1},v_{3})$ and the closest vertex
to $b$ is $v_{2}$, as desired.

  * •

If $k$ is even, start with $b$ and $v_{2}$ at distance $k-1$. Set $O_{1}$ to
be the point at distance $\frac{k}{2}-1$ from $b$ and $O_{2}$ the point at
distance $\frac{k}{2}-1$ from $v_{2}$. Add $v_{1}$ at distance $\frac{k}{2}$
from $O_{1}$ and $v_{3}$ at distance $\frac{k}{2}$ from $O_{2}$. Then $b$ is
at distance $k-1$ from $v_{1}$ and $k$ from $v_{3}$, while $v_{2}$ is at
distance $k$ from $v_{1}$ and $k-1$ from $v_{3}$. Note that $v_{1}$ and
$v_{3}$ are at distance $k+1$ from each other. Thus, the only distance which
is greater than $k$ is $d(v_{1},v_{3})$ and the closest vertex to $b$ is
$v_{2}$, as desired.

This lemma follows. ∎

###  3.3 The Interior Gadget

Lastly, we have the most complex construction, that of the interior gadget,
$I$. Now we require the following lemma which, again, is a consequence of the
4-Point Condition.

######  Lemma 3.3.

If $d(t,x_{1})\leq\min\left\\{d(t,x_{2}),d(t,x_{3})\right\\}$ and
$d(y,x_{1})>\max\left\\{d(y,x_{2}),d(y,x_{3})\right\\}$, then:

$d(t,x_{1})+d(x_{2},x_{3})<d(t,x_{2})+d(x_{1},x_{3})=d(t,x_{3})+d(x_{1},x_{2})$

###### Proof.

Assume that
$d(t,x_{1})+d(x_{2},x_{3})\geq\max\left\\{d(t,x_{2})+d(x_{1},x_{3}),d(t,x_{3})+d(x_{1},x_{2})\right\\}$.
Then, by using this assumption and our bound on $d(t,x_{1})$, we get:

$\displaystyle d(x_{2},x_{3})$
$\displaystyle\geq\max\left\\{d(x_{1},x_{3})+(d(t,x_{2})-d(t,x_{1})),d(x_{1},x_{2})+(d(t,x_{3})-d(t,x_{1}))\right\\}$
$\displaystyle\geq\max\left\\{d(x_{1},x_{3}),d(x_{1},x_{2})\right\\}$

Then, by combining this bound with our bound on $d(y,x_{1})$, we get:

$d(y,x_{1})+d(x_{2},x_{3})>\max\left\\{d(y,x_{2})+d(x_{1},x_{3}),d(y,x_{3})+d(x_{1},x_{2})\right\\}$

This contradicts Theorem 3.1. This implies that the assumption is wrong, that
is, we must have:

$d(t,x_{1})+d(x_{2},x_{3})<\max\left\\{d(t,x_{2})+d(x_{1},x_{3}),d(t,x_{3})+d(x_{1},x_{2})\right\\}.$

Now, assume without loss of generality that $d(t,x_{2})+d(x_{1},x_{3})\geq
d(t,x_{3})+d(x_{1},x_{2})$. Then, by Theorem 3.1, we must have
$d(t,x_{2})+d(x_{1},x_{3})\leq\max\left\\{d(t,x_{1})+d(x_{2},x_{3}),d(t,x_{3})+d(x_{1},x_{2})\right\\}$.
Since $d(t,x_{2})+d(x_{1},x_{3})>d(t,x_{1})+d(x_{2},x_{3})$, this implies that
$d(t,x_{2})+d(x_{1},x_{3})\leq d(t,x_{3})+d(x_{1},x_{2})$. So we get that
$d(t,x_{2})+d(x_{1},x_{3})$ is bounded above and below by
$d(t,x_{3})+d(x_{1},x_{2})$ so they must be equal.

So we get:

$d(t,x_{1})+d(x_{2},x_{3})<d(t,x_{2})+d(x_{1},x_{3})=d(t,x_{3})+d(x_{1},x_{2}).$

This completes the proof. ∎

We will also use the following simple lemma:

######  Lemma 3.4.

For any 3 leaves $u,v,w$ of a tree, $d(u,v)+d(u,w)+d(v,w)$ is even.

###### Proof.

Since we have a tree, there is a unique vertex $O$ which is simultaneously in
the path from $u$ to $v$, the path from $v$ to $w$ and the path from $u$ to
$w$.

Hence $d(u,v)+d(u,w)+d(v,w)=2\cdot(d(u,O)+d(v,O)+d(w,O))$ which must be even.
∎

We now have all the tools needed to prove our critical lemma for the interior
gadget.

See 2.3

Before proving this lemma, let’s discuss the requirement that $k\geq 5$. First
observe that no such graph can exist for $k\leq 2$ because if $m_{T}(b_{I})=3$
then $b_{I}$ is an isolated vertex in $I$. Thus its distance to other leaves
does not matter as long as it’s large enough, so the lemma could not hold.
Similarly, if $k=3$, the existence of a $3$-leaf root $T_{I}$ implies that
$b_{I}$ is not an isolated vertex in $I$. But the existence of a $3$-leaf root
$R_{I}$ implies that $b_{I}$ is an isolated vertex, a contradiction. Finally,
for $k=4$, while there is no direct simple proof that the statement does not
hold for any graph, the existence of a characterization of $4$-leaf powers
implies that no such graph can exist.

###### Proof.

For convenience, we denote $t_{I}$ and $b_{I}$ by $t$ and $b$, respectively.
To prove the lemma, we will explicitly construct $I$ for any value of $k\geq
5$. In order to do so, we consider two cases depending, again, upon the parity
of $k$.

For $k$ odd, set $q=\frac{k-1}{2}$. In particular, for $k\geq 5$ we must have
$q\geq 2$.

We construct the graph $I$ using the following sets of vertices:

  * •

$t$ and $b$

  * •

$X=\left\\{x_{1},\dots,x_{q}\right\\}$

  * •

$Y=\left\\{y_{2},\dots,y_{q}\right\\}$

The edge set is defined as follows:

  * •

For $i=1,\dots q$, $(t,x_{i})$ and $(b,x_{i})$ are edges. That is, $t$ and $b$
are adjacent to all vertices in $X$.

  * •

For $i=1,\dots,q$, for $j=i+1,\dots q$, $(x_{i},x_{j})$ is an edge. That is,
$X$ forms a clique.

  * •

For $i=2\dots q$, for $j=i\dots q$, $(y_{i},x_{j})$ is an edge.

  * •

$(b,y_{q})$ is an edge.

Equivalently, it will be helpful to define the set of edges using the
neighborhood of each vertex:

  * •

$t$ is adjacent to $X=\left\\{x_{1},\dots,x_{q}\right\\}$.

  * •

$b$ is adjacent to $X$ and to $y_{q}$.

  * •

For $i=1,\dots,q$, $x_{i}$ is adjacent to $t$, to $b$, to
$X\setminus\\{x_{i}\\}$ and to $y_{j}$ for $j=2,\dots,i$ (with $x_{1}$ having
no neighbor in $Y$).

  * •

For $i=2,\dots,q$, for $j=i,\dots,q$, $y_{i}$ is adjacent to $x_{j}$. If
$i=q$, then $y_{q}$ is also adjacent to $b$.

That is, we take $I=(V,E)$ to be defined by:

$\displaystyle V=$
$\displaystyle\left\\{t,b\right\\}\cup\left(\bigcup_{i=1}^{q}\left\\{x_{i}\right\\}\right)\cup\left(\bigcup_{i=2}^{q}\left\\{y_{i}\right\\}\right)$
(1) $\displaystyle E=$
$\displaystyle\left(\bigcup_{i=1}^{q}\left\\{(t,x_{i}),(b,x_{i})\right\\}\right)\cup\left(\bigcup_{1\leq
i<j\leq q}\left\\{(x_{i},x_{j})\right\\}\right)\cup\left(\bigcup_{2\leq i\leq
j\leq q}\left\\{(y_{i},x_{j})\right\\}\right)\cup\left\\{(b,y_{q})\right\\}$

This construction is illustrated in Figure 5. We remark that this construction
only makes sense for $k\geq 5$ because if $k=3$ or $k=1$ then $Y$ is not well
defined.

$t$$b$$x_{1}$$x_{2}$$x_{3}$$\vdots$$x_{q-2}$$x_{q-1}$$x_{q}$$X$
(Clique)$y_{2}$$y_{3}$$\vdots$$y_{q-2}$$y_{q-1}$$y_{q}$ Figure 5: The interior
gadget $I$ for odd $k$. The bold edges signify all possible connections are
made.

We will prove that this graph satisfies the lemma by proving three claims.

######  Claim 3.5.

For $I$ as defined in (1):

For all $k$-leaf roots $T$ of $I$, $m_{T}(t)=k\Longrightarrow m_{T}(b)=3$.

###### Proof.

Assume that $m_{T}(t)=k$, then $\forall i\in[q]$, $d(t,x_{i})=k$. Then for all
distinct $i,j\in[q]$, by Lemma 3.4 with $t$, $x_{i}$ and $x_{j}$,
$d(x_{i},x_{j})$ must be even (and, thus, at most $k-1$).

Assume $i<j<\ell$. Then
$d(t,x_{i})=k=\min\left\\{d(t,x_{j}),d(t,x_{\ell})\right\\}$. Furthermore,
$d(y_{j},x_{i})>k\geq\max\left\\{d(y_{j},x_{j}),d(y_{j},x_{\ell})\right\\}$
because $y_{j}$ is adjacent to $x_{j}$ and $x_{\ell}$ but not $x_{i}$ (nor
$t$). So, by Lemma 3.3, we get:

$\displaystyle
d(t,x_{i})+d(x_{j},x_{\ell})<d(t,x_{\ell})+d(x_{i},x_{j})=d(t,x_{j})+d(x_{i},x_{\ell})$

But because $d(t,x_{i})=d(t,x_{j})=d(t,x_{\ell})=k$. This is true if and only
if

$\displaystyle d(x_{j},x_{\ell})<d(x_{i},x_{j})=d(x_{i},x_{\ell})$

This implies that for every $i\in[q-1]$, there exists some integer
$\lambda_{i}$ such that
$d(x_{i},x_{i+1})=d(x_{i},x_{i+2})=\dots=d(x_{i},x_{q})=\lambda_{i}$.
Moreover, as shown, the $\lambda_{i}$ must be even. Thus
$k-1\geq\lambda_{1}>\dots>\lambda_{q-1}>2$. By definition, $2q=k-1$. In
particular, there are only $q-1$ even numbers greater that $2$ and at most
$k-1$. Therefore, $\lambda_{i}=k+1-2i$. Specifically, we have shown that
$d(x_{i},x_{j})=k+1-2i$, for $1\leq i<j\leq q$.

Recall $d(t,x_{i})=k=\min\left\\{d(t,x_{q}),d(t,b)\right\\}$ and
$d(y_{q},x_{i})>k\geq\max\left\\{d(y_{q},x_{q}),d(y_{q},b)\right\\}$, for
$i<q$. So, by Lemma 3.3, we obtain:

$d(x_{q},b)+d(x_{i},t)<d(x_{q},x_{i})+d(t,b)=d(x_{q},t)+d(x_{i},b).$

Consider $i=1$. Recall $k\geq 5$ and $q\geq 2$. So $q\neq 1$ implying that
$x_{q}\neq x_{1}$. It follows that

$\displaystyle\ d(x_{1},x_{q})+d(t,b)=d(x_{q},t)+d(x_{1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ k-1+d(t,b)=k+d(x_{1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ d(t,b)=1+d(x_{1},b)$

However, we must have $d(t,b)>k$ and $d(x_{1},b)\leq k$. So it must be that
$d(t,b)=k+1$ and $d(x_{1},b)=k$.

Next consider $i=q-1$. Because $q\geq 2$, we have $i\geq 1$ and so $x_{q-1}$
exists. Then $d(x_{q-1},x_{q})=k+1-2(q-1)=k+3-(k-1)=4$. Therefore, because
$d(x_{i},t)=k$ for all $1\leq i\leq q$, we have

$\displaystyle\ d(x_{q-1},x_{q})+d(t,b)=d(x_{q},t)+d(x_{q-1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ 4+k+1=k+d(x_{q-1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ d(x_{q-1},b)=5$

Finally, recall that $d(x_{q},b)+d(x_{q-1},t)<d(x_{q},x_{q-1})+d(t,b)$. This
implies that $d(x_{q},b)+k<4+(k+1)$. In particular, $d(x_{q},b)<5$. Moreover,
by Lemma 3.4, we know $d(x_{q},b)+d(x_{q},x_{q-1})+d(x_{q-1},b)$ is even. But
$d(x_{q},x_{q-1})$ is even and $d(x_{q-1},b)$ is odd. Hence $d(x_{q},b)$ must
be odd. In particular, it must be odd and less than 5. Hence $d(x_{q},b)=3$,
which is what we wanted to show. ∎

######  Claim 3.6.

For $I$ as defined in (1):

There exists a $k$-leaf root $T_{I}$ of $I$ such that $m_{T_{I}}(t)=k$ and
$m_{T_{I}}(b)=3$.

###### Proof.

We will prove this by explicitly constructing a leaf root. Recall $k$ is odd
and $k=2q+1$.

  1. 1.

Take a path of length $k+1=2q+2$ from $t$ to $b$.

  2. 2.

Label the vertices along the path from $t$ to $b$ which are at distance $q+i$
of $t$ as $O_{i}$ for $i=1,\dots,q+1$.

  3. 3.

Add a path of length $q-i+1$ from $O_{i}$ to $x_{i}$ for $i=1,\dots,q$.

  4. 4.

Add a path of length $k-2$ from $O_{q+1}$ to $y_{q}$.

  5. 5.

If $k\geq 7$, add a path of length $q+i$ from $O_{i}$ to $y_{i}$ for
$i=2,\dots,q-1$. (For $k=5$ we have $q=2$, so these $y_{i}$ do not exist.)

$t$$O_{1}$$O_{2}$$O_{3}$$x_{1}$$x_{2}$$x_{3}$$y_{2}$$y_{3}$$\dots$$\dots$$\dots$$O_{q-2}$$O_{q-1}$$O_{q}$$O_{q+1}$$x_{q-2}$$x_{q-1}$$x_{q}$$y_{q-2}$$y_{q-1}$$y_{q}$$b$$q+1$$q$$q-1$$q-2$$q+2$$q+3$$3$$2$$1$$k-3$$k-2$$k-2$1
Figure 6: The $k$-leaf root $T_{I}$ of the interior gadget for odd $k=2q+1$.
(Recall these will be connected in series below the leaf root of the top
gadget; see Figure 2.)

This construction is shown in Figure 6. It remains to verify that this is a
valid $k$-leaf root of $I$, that is, the leaf vertices at distance at most $k$
in the tree are exactly the edges of $I$. The required case analysis follows.

  * •

The path from $t$ to $b$ has length $k+1>k$ and $t$ and $b$ are not neighbors,
as desired.

  * •

For $i=1,\dots,q$, the path from $t$ to $x_{i}$ goes through $O_{i}$. That is,
it is the path from $t$ to $O_{i}$ which has length $q+i$ followed by the path
from $O_{i}$ to $x_{i}$ which has length $q-i+1$. So, the path from $t$ to
$x_{i}$ has length $(q+i)+(q-i+1)=k$.

  * •

The path from $t$ to $y_{q}$ goes through $O_{q+1}$, so it has length
$(2q+1)+(k-2)>k$.

  * •

For $i=1,\ldots,q$, the path from $b$ to $x_{i}$ goes through $O_{q}$ and
$O_{i}$ so it has length $2+(q-i)+(q-i+1)\leq k$. In particular, for $i=q$,
the path from $b$ to $x_{q}$ has length $3$.

  * •

The path from $b$ to $y_{q}$ goes through $O_{q+1}$ so it has length
$1+(k-2)\leq k$

  * •

For $1\leq i<j\leq q$, the path from $x_{i}$ to $x_{j}$ goes through $O_{i}$
and $O_{j}$ so it has length $(q-i+1)+(j-i)+(q-j+1)\leq k$

  * •

For $i=1,\ldots,q$ and $j=2,\ldots,q-1$, the path from $x_{i}$ to $y_{j}$ goes
through $O_{i}$ and $O_{j}$ (possibly the same vertex) so it has length
$(q-i+1)+(|i-j|)+(q+j)=k+(j-i)+|i-j|$ which is at most $k$ if and only if
$i\geq j$.

  * •

For $i=1,\ldots,q$, the path from $x_{i}$ to $y_{q}$ goes through $O_{i}$ and
$O_{q+1}$ so it has length $(q-i+1)+(q+1-i)+(k-2)$ which is equal to $k$ if
$i=q$ and strictly greater than $k$ otherwise.

For $k=5$ the case analysis is complete. If $k\geq 7$ then $q\geq 3$ and so
$|Y|>1$. Thus we have four more cases to verify:

  * •

For $i=2,\ldots,q-1$, the path from $t$ to $y_{i}$ goes through $O_{i}$, so it
has length $(q+i)+(q+i)>k$.

  * •

For $i=2,\ldots,q-1$, the path from $b$ to $y_{i}$ goes through $O_{q}$ and
$O_{i}$ so it has length $2+(q-i)+(q+i)>k$.

  * •

For $2\leq i<j\leq q-1$, the path from $y_{i}$ to $y_{j}$ goes through $O_{i}$
and $O_{j}$, so it has length $(q+i)+(j-i)+(q+j)>k$.

  * •

For $i=2,\ldots,q-1$, the path from $y_{i}$ to $y_{q}$ goes through $O_{i}$
and $O_{q+1}$ so it has length $(q+i)+(q+1-i)+(k-2)>k$.

Hence the desired $k$-leaf root exists. ∎

It remains to prove the final property to conclude that the claim holds when
$k$ is odd:

######  Claim 3.7.

For $I$ as defined in (1):

There exists a $k$-leaf root $R_{I}$ of $I$ such that $m_{R_{I}}(t)=k-1$ and
$m_{R_{I}}(b)=4$.

###### Proof.

To construct $R_{I}$ we make two minor modifications to the tree $T_{I}$ used
to prove Claim 3.6. First we start with a path of length $k+2$ from $t$ to
$b$. To do this we simply place $b$ at distance $2$ from $O_{q+1}$ instead of
$1$. All the remaining vertices are then placed using the same process except
for $x_{1}$ which is now at distance $q-1$ from $O_{1}$ instead of at distance
$q$. The resultant tree is shown in Figure 7.

$t$$O_{1}$$O_{2}$$O_{3}$$x_{1}$$x_{2}$$x_{3}$$y_{2}$$y_{3}$$\dots$$\dots$$\dots$$O_{q-2}$$O_{q-1}$$O_{q}$$O_{q+1}$$x_{q-2}$$x_{q-1}$$x_{q}$$y_{q-2}$$y_{q-1}$$y_{q}$$b$$q+1$$q-1$$q-1$$q-2$$q+2$$q+3$$3$$2$$1$$k-3$$k-2$$k-2$2
Figure 7: The $k$-leaf root $R_{I}$ of the interior gadget for odd $k=2q+1$.
(Recall these will be connected in series above the leaf root of the bottom
gadget; see Figure 2.)

It suffices to verify that all the vertices are still at a correct distance
from $x_{1}$ and from $b$.

  * •

The distance from $x_{1}$ to all other vertices except $b$ has decreased by
$1$ so we need to verify that the $y_{i}$ and $y_{q}$ are still at distance at
least $k+1$. For $i=2,\ldots,q-1$, the distance from $x_{1}$ to $y_{i}$ is
$(q-1)+(i-1)+(q+i)>k$ (since $i\geq 2$). The distance from $x_{1}$ to $y_{q}$
is $(q-1)+q+(k-2)=2q+k-3>k$ (since $q\geq 2$).

  * •

The distance from $b$ to all other vertices except $x_{1}$ has increased by
$1$ so we need to verify that the $x_{i}$’s and $y_{q}$ are still at distance
at most $k$. For $i\geq 2$, the distance from $b$ to $x_{i}$ is
$3+(q-i)+(q-i+1)\leq k$. The distance from $b$ to $y_{q}$ is $2+(k-2)=k$.
Moreover, all distances from $b$ to an $x_{i}$ vertex are now at least $4$ and
not $3$ (including $x_{1}$, which is at distance $k=2q+1$ from $b$). In
particular, the distance between $b$ and $x_{q}$ is exactly $4$.

Observing that $t$ is now at distance $k-1$ from $x_{1}$ and is still at
distance $k$ to its other neighbors, we get $m_{R_{I}}(t)=k-1$ and
$m_{R_{I}}(b)=4$. Hence the desired $k$-leaf root exists. ∎

We have now proven the result holds for $k$ odd. Let’s now prove it for $k$
even. The construction of the graph $I$ for even values of $k$ is very similar
to the construction for odd values of $k$, but is slightly more intricate.
Take $q=\frac{k}{2}$. The vertex set of $G$ is then

  * •

$t$ and $b$

  * •

$X=\left\\{x_{1},\dots,x_{q}\right\\}$

  * •

$Y=\left\\{y_{2},\dots,y_{q}\right\\}$

  * •

$z_{1}$ and $z_{2}$.

The edge set of $G$ is defined as follows:

  * •

$(t,x_{1})$ is an edge and $\forall i=2,\dots q$, $(t,x_{i})$, $(b,x_{i})$,
$(z_{1},x_{i})$ and $(z_{2},x_{i})$ are all edges. That is, $t$ is adjacent to
all vertices in $X$ while $b$, $z_{1}$ and $z_{2}$ are adjacent to all
vertices in $X$ except $x_{1}$.

  * •

For $i=1,\dots,q$, for $j=i+1,\dots q$, $(x_{i},x_{j})$ is an edge. That is,
$X$ forms a clique.

  * •

For $i=2,\dots,q$, for $j=i,\dots,q$, $(y_{i},x_{j})$ is an edge.

  * •

$(b,y_{q})$ is an edge.

  * •

$(z_{1},b)$ and $(z_{2},b)$ are both edges, in particular, for all $i\geq 2$,
$\left\\{z_{1},z_{2},b,x_{i}\right\\}$ will form a diamond (with the
$(z_{1},z_{2})$ edge being missing).

Equivalently, it is again informative to define the set of edges using the
neighborhoods of each vertex:

  * •

$t$ and $x_{1}$ are adjacent to each other and to $X$.

  * •

$b$ is adjacent to $X\setminus\\{x_{1}\\}$, to $y_{q}$ and to $z_{1}$ and
$z_{2}$.

  * •

For $i=2,\dots q$, $x_{i}$ is adjacent to $t$, $b$, $z_{1}$, $z_{2}$,
$X\setminus\\{x_{i}\\}$ and to $y_{j}$ for $j=1,\dots,i$.

  * •

For $i=2,\dots,q$, for $j=i,\dots,q$, $y_{i}$ is adjacent to $x_{j}$.

  * •

$y_{q}$ is adjacent to $x_{q}$ and $b$.

  * •

$z_{1}$ and $z_{2}$ are adjacent to $X\setminus\\{x_{1}\\}$ and to $b$.

$t$$b$$x_{1}$$x_{2}$$x_{3}$$\vdots$$x_{q-2}$$x_{q-1}$$x_{q}$$X$
(Clique)$y_{2}$$y_{3}$$\vdots$$y_{q-2}$$y_{q-1}$$y_{q}$$z_{1}$$z_{2}$ Figure
8: The interior gadget for even $k$.

That is, we take $I=(V,E)$ to be defined by:

$\displaystyle V=$
$\displaystyle\left\\{t,b,z_{1},z_{2}\right\\}\cup\left(\bigcup_{i=1}^{q}\left\\{x_{i}\right\\}\right)\cup\left(\bigcup_{i=2}^{q}\\{y_{i}\\}\right)$
(2) $\displaystyle E=$
$\displaystyle\left\\{(t,x_{1})\right\\}\cup\left(\left\\{\bigcup_{i=2}^{q}\left\\{(t,x_{i}),(b,x_{i}),(z_{1},x_{i}),(z_{2},x_{i})\right\\}\right\\}\right)$
$\displaystyle\qquad\cup\left(\bigcup_{1\leq i<j\leq
q}\left\\{(x_{i},x_{j})\right\\}\right)\cup\left(\bigcup_{2\leq i\leq j\leq
q}\left\\{(y_{i},x_{j})\right\\}\right)\cup\left\\{(b,y_{q}),(z_{1},b),(z_{2},b)\right\\}$

This construction is illustrated in Figure 8. We remark that this construction
only makes sense for $k\geq 4$. If $k=2$ then $Y$ is not well defined. But,
while the construction makes sense for $k=4$, we will show later where it
fails to work.

Recall $z_{1}$ and $z_{2}$ form a diamond with $b$ and $x_{i}$ for any $i\geq
2$. Therefore, by Corollary 3.2, we have that $d(b,x_{i})\neq k$ in any
$k$-leaf root, in particular this is true for $i=2$ so we get $d(b,x_{2})\neq
k$.

######  Claim 3.8.

For $I$ as defined in (2):

For all $k$-leaf roots $T$ of $I$, $m_{T}(t)=k\Longrightarrow m_{T}(b)=3$.

###### Proof.

Most of the arguments used to prove Claim 3.5 are still valid. Using Lemma 3.3
we can show that $d(x_{i},x_{j})=k+2-2i$. Furthermore, since $k\geq 6$, $q\geq
3$ and for $2\leq i\leq q-1$, we have
$d(x_{q},b)+d(x_{i},t)<d(x_{i},x_{q})+d(t,b)=d(x_{q},t)+d(x_{i},b)$.

However $(x_{1},b)$ is not an edge in this case so instead we must consider
$i=2$. Now we get:

$\displaystyle\ d(x_{q},x_{2})+d(t,b)=d(x_{q},t)+d(x_{2},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ k-2+d(t,b)=k+d(x_{2},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ d(t,b)=2+d(x_{2},b)$

Moreover, we must have $d(t,b)>k$ and $d(x_{2},b)\leq k$. So we get either
$d(t,b)=k+2$ and $d(x_{2},b)=k$ or $d(t,b)=k+1$ and $d(x_{2},b)=k-1$. But we
cannot have $d(x_{2},b)=k$ as this violates Corollary 3.2 when considering the
diamond $(b,z_{1},x_{2},z_{2})$. Hence, we must have $d(x_{2},b)=k-1$ and
$d(t,b)=k+1$.

Next, as in Claim 3.5, consider $i=q-1$. Then as
$d(x_{q-1},x_{q})=k+2-2(q-1)=k+2-(k-2)=4$, we get

$\displaystyle\ d(x_{q-1},x_{q})+d(t,b)=d(x_{q},t)+d(x_{q-1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ 4+k+1=k+d(x_{q-1},b)$
$\displaystyle\Longrightarrow$ $\displaystyle\ d(x_{q-1},b)=5$

As before, we have shown that
$d(x_{q},b)+d(x_{q-1},t)<d(x_{q},x_{q-1})+d(t,b)$. This implies
$d(x_{q},b)+k<4+(k+1)$ and so $d(x_{q},b)<5$. Moreover, by Lemma 3.4,
$d(x_{q},b)+d(x_{q},x_{q-1})+d(x_{q-1},b)$ is even. Consequently $d(x_{q},b)$
must be odd. But $d(x_{q},x_{q-1})=4$ is even and $d(x_{q-1},b)=5$ is odd.
Thus $d(x_{q},b)$ must be odd and less than 5. Hence $d(x_{q},b)=3$, as
desired. ∎

######  Claim 3.9.

For $I$ as defined in 2:

There exists a $k$-leaf root $T_{I}$ of $I$ such that $m_{T_{I}}(t)=k$ and
$m_{T_{I}}(b)=3$.

###### Proof.

We construct $I$ similarly to the proof of Claim 3.6. Recall that $k=2q$.

  1. 1.

Take a path of length $k+1$ from $t$ to $b$.

  2. 2.

Label as $O_{i}$ the vertex along the path from $t$ to $b$ at distance $q-1+i$
from $t$, for $i=1,\dots,q+1$.

  3. 3.

Add a path of length $q-i+1$ from $O_{i}$ to $x_{i}$ for $i=1,\dots,q$.

  4. 4.

Add a path of length $q+i-1$ from $O_{i}$ to $y_{i}$ for $i=2,\dots,q-1$.

  5. 5.

Add a path of length $k-2$ from $O_{q+1}$ to $y_{q}$.

  6. 6.

Add a path of length $q$ from $O_{2}$ to $z_{1}$ and a path of length $q$ from
$O_{3}$ to $z_{2}$. (Since $k\geq 6$ we have $q\geq 3$ and, so, both $O_{2}$
and $O_{3}$ exist.)

$t$$O_{1}$$O_{2}$$O_{3}$$x_{1}$$x_{2}$$x_{3}$$y_{2}$$y_{3}$$\dots$$\dots$$\dots$$O_{q-2}$$O_{q-1}$$O_{q}$$O_{q+1}$$x_{q-2}$$x_{q-1}$$x_{q}$$y_{q-2}$$y_{q-1}$$y_{q}$$b$$z_{1}$$z_{2}$$q$$q$$q-1$$q-2$$q+1$$q+2$$3$$2$$1$$k-3$$k-2$$k-2$1$q$$q$
Figure 9: The $k$-leaf root $R_{I}$ of the interior gadget for even $k=2q$.
(Recall these will be connected in series below the leaf root of the top
gadget; see Figure 2.)

This graph $T_{I}$ is shown in Figure 9. We must show $T_{I}$ is a $k$-leaf
root of $I$. The fact that these distances are valid follows from Claim 3.6
with the modification that $k=2q$. It remains to verify that $z_{1}$ and
$z_{2}$ also have the correct neighborhoods.

  * •

For all $i=2,\dots,q$, the vertices $t$, $x_{1}$, $y_{q}$, and $y_{i}$ are at
distance at least $q+1$ from $O_{2}$ and $O_{3}$. Thus, they are at distance
at least $2q+1>k$ from $z_{1}$ and $z_{2}$.

  * •

For $i=2,\dots,q$, the vertices $x_{i}$ and $b$ are both at distance at most
$q$ from $O_{2}$ and from $O_{3}$. Thus they are all within distance $2q=k$
from $z_{1}$ and $z_{2}$.

  * •

The path from $z_{1}$ to $z_{2}$ goes through both $O_{2}$ and $O_{3}$ so it
has length $q+1+q>k$.

Hence the desired $k$-leaf root $T_{I}$ exists. ∎

######  Claim 3.10.

For $I$ as defined in 2:

There exists a $k$-leaf root $R_{I}$ of $I$ such that $m_{R_{I}}(t)=k-1$ and
$m_{R_{I}}(b)=4$.

###### Proof.

To construct $R_{I}$ we make four minor modifications to the tree $T_{I}$ used
to prove Claim 3.9. First we start with a path of length $k+2$ from $t$ to
$b$. To do this we simply place $b$ at distance $2$ from $O_{q+1}$ instead of
$1$. Second, we place $x_{2}$ at distance $q-2$ from $O_{1}$ instead of at
distance $q-1$. Third and fourth, we place $z_{1}$ and $z_{2}$ at distance $q$
from $O_{3}$ and $O_{4}$, respectively. The resultant tree is shown in Figure
10.

$t$$O_{1}$$O_{2}$$O_{3}$$O_{4}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{2}$$y_{3}$$y_{4}$$\dots$$\dots$$\dots$$O_{q-2}$$O_{q-1}$$O_{q}$$O_{q+1}$$x_{q-2}$$x_{q-1}$$x_{q}$$y_{q-2}$$y_{q-1}$$y_{q}$$b$$z_{1}$$z_{2}$$q$$q$$q-2$$q-2$$q-3$$q+1$$q+2$$q+3$$3$$2$$1$$k-3$$k-2$$k-2$2$q$$q$
Figure 10: The $k$-leaf root $R_{I}$ of the interior gadget for even $k=2q$.
(Recall these will be connected in series above the leaf root of the bottom
gadget; see Figure 2.)

We emphasize that this construction is NOT possible for $k=4$. This is because
then $q=2$ and $O_{4}$, the vertex $O_{4}$ does not exist. Thus this
construction applies for even $k\geq 6$.

Finally, as in the proof of Claim 3.7, these changes do not change the
neighborhood of the displaced vertices $b$ and $x_{2}$, $z_{1}$ and $z_{2}$.
Hence the desired $k$-leaf root exists. ∎

This completes the proof of the lemma. ∎

With our three critical lemmas proven, the main theorem now holds by the
method shown in Section 2.

##  4 Linear Leaf Powers

A caterpillar is a graph which has a central path and a set of leaves whose
neighbor is on the central path. A graph is said to be a linear leaf power if
it has a leaf root which is the subdivision of a caterpillar. Such a leaf root
is called a linear leaf root [2].

Our results apply not only to general leaf powers but also to this variant.
Indeed, even if we restrict to having a subdivision of a caterpillar as a leaf
root, it is impossible to get a simple forbidden subgraph characterization of
linear $k$-leaf powers for $k\geq 5$.

######  Theorem 4.1.

For $k\geq 5$, the set of linear $k$-leaf powers cannot be written as the set
of strongly chordal graphs which are $\mathscr{F}_{k}$-free where
$\mathscr{F}_{k}$ is a finite set of graphs.

As in the general case, we prove this using three gadgets. However, we must
now add a condition to ensure that merging the gadgets preserves having a
subdivision of a caterpillar as a leaf root.

######  Lemma 4.2.

For all $k\geq 5$ there exists a gadget graph Top that contains a vertex $t\in
V(\text{Top})$ such that:

  1. 1.

For any linear $k$-leaf root $T$ of Top, $m_{T}(t)=3$.

  2. 2.

There exists a linear $k$-leaf root $T_{\text{Top}}$ of Top where $t$ is a
neighbor of the last node of the central path.

######  Lemma 4.3.

For all $k\geq 5$ there exists a gadget graph Bot that contains a vertex $b\in
V(\text{Bot})$ such that:

  1. 1.

For any linear $k$-leaf root $T$ of Bot, $m_{T}(b)\leq k-1$.

  2. 2.

There exists a linear $k$-leaf root $T_{\text{Bot}}$ such that
$m_{T_{\text{Bot}}}(b)=k-1$ where $b$ is a neighbor of the last node of the
central path.

######  Lemma 4.4.

For all $k\geq 5$ there exists a gadget graph $I$ that contains two distinct
vertices $t_{I},b_{I}\in V(I)$ such that:

  1. 1.

For all linear $k$-leaf roots $T$ of $I$, $m_{T}(t_{I})\geq k\Longrightarrow
m_{T}(b_{I})=3$.

  2. 2.

There exists a linear $k$-leaf root $T_{I}$ of $I$ such that
$m_{T_{I}}(t_{I})=k$ and $m_{T_{I}}(b_{I})=3$ where $b$ and $t$ are neighbors
of the first and last node of the central path respectively.

  3. 3.

There exists a linear $k$-leaf root $R_{I}$ of $I$ such that
$m_{R_{I}}(t_{I})=k-1$ and $m_{R_{I}}(b_{I})=4$ where $b$ and $t$ are
neighbors of the first and last node of the central path respectively.

Merging the gadgets is identical to before except that we now use the
condition that, in each gadget, $t$ and/or $b$ are neighbors of the extremal
vertices of the central path. This means when merging the gadgets using the
parent of these vertices, we merge the central paths by their endpoint to
create a longer path, ensuring we produce another caterpillar subdivision.

We can verify that Lemma 4.3 follows from Lemma 2.2 and Lemma 4.4 follows from
Lemma 2.3, as our constructions for the interior gadget and the Bottom Gadget
used for the general case satisfy the properties needed, namely the leaf root
used in the proofs are subdivisions of caterpillars with the required vertices
connected to the extremal vertices of the central path. On the other hand, the
graph used to construct the Top Gadget does not satisfy this property444The
Top Gadget for the case of general $k$-leaf powers is a caterpillar but the
vertex $t$ used is not connected to an extremal vertex of the central path.;
so we need to construct a new graph for Top.

###### Proof of Lemma 4.2.

The gadget graph Top consists of a $k-1$ clique with vertices
$X=\left\\{x_{1},\dots,x_{k-1}\right\\}$, to which we add vertices
$Y=\left\\{y_{0},\dots,y_{k}\right\\}$ such that the neighborhood of $y_{i}$
is $X\cap\left\\{x_{i-1},x_{i},x_{i+1}\right\\}$ (that is, $y_{i}$ has 3
neighbors if $i=2,\dots,k-2$, $y_{1}$ and $y_{k-1}$ have two neighbors and
$y_{0}$ and $y_{k}$ have one neighbor). This gadget is illustrated in Figure
11555We remark that a more careful analysis of this family of graphs might
also work for the general case..

$x_{1}$$x_{2}$$x_{3}$$\dots$$x_{k-3}$$x_{k-2}$$x_{k-1}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$\dots$$y_{k-3}$$y_{k-2}$$y_{k-1}$$y_{k}$
Figure 11: The top gadget for linear leaf roots.

Let $T$ be any linear $k$-leaf root of Top. For $1\leq i\leq k-1$, let $O_{i}$
be the vertex on the central path closest to $x_{i}$ in $T$. We wish to show
that for $1\leq i<j\leq k-1$, $O_{i}\neq O_{j}$. For a contradiction, assume
that $O_{i}=O_{j}=O$, for some $i<j$. Now consider $y_{i-1}$ and $y_{j+1}$.
Since $i<j$, $y_{i-1}$ is not a neighbor of $x_{j}$ and $y_{j+1}$ is not a
neighbor of $x_{i}$ in Top. In $T$, every path from a leaf to $x_{i}$ or to
$x_{j}$ must go through $O$. In particular, for all leaves $v$ of $T$ we have
$d(x_{i},O)-d(x_{j},O)=d(x_{i},v)-d(x_{j},v)$. However, we must have
$d(x_{i},y_{i-1})<d(x_{j},y_{i-1})$ and $d(x_{i},y_{j+1})>d(x_{j},y_{j+1})$.
This implies that
$0>d(x_{i},y_{i-1})-d(x_{j},y_{i-1})=d(x_{i},O)-d(x_{j},O)=d(x_{i},y_{j+1})-d(x_{j},y_{j+1})>0$,
a contradiction. Thus $O_{i}\neq O_{j}$.

Since $X$ forms a clique, all of its vertices must be within distance $k$ from
one another in $T$. Moreover, they must also all be connected to a different
vertex of the path. Let $\ell$ and $r$ be the endpoints of the central path.
Let $O_{\ell}$ be the $O_{i}$ closest one to $\ell$ and $O_{r}$ the closest
one to $r$. (Note that $O_{\ell}$ and $O_{r}$ are not necessarily $\ell$ and
$r$ since these only take into account $X$ and not $Y$.)

Every $O_{i}$ must be contained in the path from $O_{\ell}$ to $O_{r}$. In
particular, the distance from $x_{\ell}$ to $x_{r}$ is $k$ if and only if
there is no vertex in the path which is not $O_{i}$ for any $i$, and both
$x_{\ell}$ and $x_{r}$ are at distance one from $O_{\ell}$ and $O_{r}$,
respectively. In particular, there exists a permutation $\sigma$ of
$\left\\{1,\dots,k-1\right\\}$ such that the path from $O_{\ell}$ to $O_{r}$
is exactly $O_{\ell}=O_{\sigma(1)}\rightarrow
O_{\sigma(2)}\rightarrow\dots\rightarrow O_{\sigma(k-2)}\rightarrow
O_{\sigma(k-1)}=O_{r}$.

Consider $x_{\sigma(1)}=x_{\ell}$ and $x_{\sigma(2)}$. By construction, one of
$y_{\sigma(2)-1}$ or $y_{\sigma(2)+1}$ is not a neighbor of $x_{\sigma(1)}$
but is a neighbor of $x_{\sigma(2)}$. Let $y_{\sigma(2)\pm 1}$ denote the one
which satisfies this property (or either of them if both satisfy it). The path
from $y_{\sigma(2)\pm 1}$ to $x_{\sigma(1)}$ and the path from
$y_{\sigma(2)\pm 1}$ to $x_{\sigma(2)}$ must both go through $O_{\sigma(1)}$
or both go through $O_{\sigma(2)}$. Since $d(x_{\sigma(1)},O_{\sigma(1)})=1$,
$x_{\sigma(1)}$ is closer to $O_{\sigma(1)}$ than $x_{\sigma(2)}$, therefore
both paths cannot go through $O_{\sigma(1)}$ otherwise $y_{\sigma(2)\pm 1}$
would be closer to $x_{\sigma(1)}$ than $x_{\sigma(2)}$. Moreover, since
$d(x_{\sigma(1)},O_{\sigma(2)})=d(x_{\sigma(1)},O_{\sigma(1)})+d(O_{\sigma(1)},O_{\sigma(2)})=2$
and $y_{\sigma(2)\pm 1}$ is closer to $O_{\sigma(2)}$ than to $O_{\sigma(1)}$,
we must have $d(x_{\sigma(2)},O_{\sigma(2)})<2$. Consequently,
$d(x_{\sigma(2)},O_{\sigma(2)})=1$. It immediately follows that
$y_{\sigma(2)\pm 1}$ is at distance $k$ from $x_{\sigma(2)}$ and at distance
$k+1$ from $x_{\sigma(1)}$.

Similarly, we can show that $x_{\sigma(1)}$ has at least one neighbor, denoted
$y_{\sigma(1)\pm 1}$, which is not a neighbor of $x_{\sigma(2)}$. This implies
that its distance to $O_{\sigma(1)}$ is $k-1$. However, all $x_{i}$, for
$i\neq\sigma(1)$, are at distance at least $2$ from $O_{\sigma(1)}$. So there
exists $y_{\sigma(1)\pm 1}$ which has no neighbor in $X$ except
$x_{\sigma(1)}$.

The same argument shows that $y_{\sigma(k-1)\pm 1}$ has no neighbor in $X$
except $x_{\sigma(k-1)}$. But the only vertices in $Y$ of degree 1 are $y_{0}$
and $y_{k}$. Therefore, either $1=\sigma(1)$ or $1=\sigma(k-1)$. In either
case $x_{1}$ is at distance exactly $3$ from another (leaf) vertex, namely,
either $x_{\sigma(2)}$ or $x_{\sigma(k-2)}$. Next observe that no two distinct
leaves of $T$ can be at distance $2$. This is because no two vertices of Top
have the same set of neighbors. Hence, taking $t=x_{1}$, we obtain
$m_{T}(t)=3$.

It remains to find a linear $k$-leaf root satisfying the second property in
the lemma. We build this tree $T_{\text{Top}}$ as follows:

  1. 1.

Take a path of length $k$ from $O_{1}$ to $O_{k-1}$.

  2. 2.

Label the vertices along the path from $x_{1}$ to $x_{k-1}$ which are at
distance $i$ from $x_{1}$ as $O_{i}$ for $i=1,\dots,k-1$.

  3. 3.

Add a path of length $1$ from $O_{i}$ to $x_{i}$ for $i=2,\dots,k-2$.

  4. 4.

Add a path of length $k-2$ from $O_{i}$ to $y_{i}$ for $i=1,\dots,k-1$.

  5. 5.

Add a path of length $k-1$ from $O_{1}$ to $y_{0}$ and from $O_{k-1}$ to
$y_{k}$.

$O_{1}$$O_{2}$$O_{3}$$x_{1}$$x_{2}$$x_{3}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$\dots$$\dots$$\dots$$O_{k-3}$$O_{k-2}$$O_{k-1}$$x_{k-3}$$x_{k-2}$$x_{k-1}$$y_{k-3}$$y_{k-2}$$y_{k-1}$$y_{k}$$k-1$$k-2$$k-2$$k-2$$k-2$$k-2$$k-2$$k-1$
Figure 12: The linear $k$-leaf root $T_{\text{Top}}$ for the top gadget.

This tree is shown in Figure 12. It is easy to verify that this tree does
induce $X$ to form a clique in its $k$-leaf power graph, and that $y_{i}$ is
only adjacent to $\left\\{x_{i-1},x_{i},x_{i+1}\right\\}\cap X$. Moreover,
taking $t=x_{1}$ again yields the desired result. ∎

We remark that this result does not immediately imply that there is no
characterization for the entire class of linear leaf powers using chordal
graphs and a finite number of forbidden induced subgraphs. We have proven that
such a characterization is impossible for each $k\geq 5$, but not necessarily
for the union over all $k$. It was proved by Bergougnoux et al. [2] that
linear leaf powers are also co-threshold tolerance. Further work on this could
include verifying whether co-threshold tolerance graphs can be characterized
using a finite number of obstructions. Furthermore, it is worth noting that,
despite Lemma 4.1, linear leaf powers are recognizable in polynomial time [2].

##  5 Acknowledgements

We would like to thank the Montreal Game Theory Workshop for helping bring
together our research group.

##  6 Conclusion

We have shown that $k$-leaf powers require a deeper characterization than
strong chordality with a finite set of forbidden induced subgraphs. Several
directions to explore remain in order to gain a more comprehensive
understanding of $k$-leaf power graphs. First, is it possible to construct
and/or characterize minimal, strongly chordal graphs that are not $k$-leaf
powers? We were able to construct graphs $H_{n}$ that _contain_ such minimal
examples as induced subgraphs; but we did not construct those examples
explicitly. Following this line of reasoning, it may be possible to
characterize $k$-leaf powers as strongly chordal graphs that also forbid an
additional infinite, but easy-to-describe family of forbidden subgraphs. A
famous example of this are interval graphs, which are the chordal graphs
containing no asteroidal triples [22].

Second, are there relevant subclasses of $k$-leaf powers that can be
characterized by strong chordality and a finite set of forbidden induced
subgraphs? For example, the $k$-leaf powers whose $k$-leaf roots admit a
subdivision of a star should be easy enough to characterize. What about
subdivisions of a tree with a small number, say two or three, of non-leaf
vertices? One may also consider the $k$-leaf powers of caterpillars (not
subdivided). Based on the midpoint arguments of Brandstädt et al. [4, Theorem
6], it would appear that, for even $k$, these coincide with the unit interval
graphs whose intervals have length $k-2$ and integer endpoints. Such (twin-
free) graphs were shown to admit a finite set of forbidden induced subgraphs
in [13]. If this characterization extends to caterpillar $k$-leaf powers, this
would show that taking subdivisions is necessary for our result on caterpillar
graphs. It may also be interesting to characterize $k$-leaf powers for other
graph classes that are known to be contained in $\mathcal{L}$; for instance,
$k$-leaf powers that are also ptolemaic graphs, interval graphs, rooted
directed path graphs, and others.

## References

  * [1] R. Ahmed, G. Bodwin, F. Sahneh, K. Hamm, M. Jebelli, S. Kobourov, and R. Spence.  Graph spanners: A tutorial review.  Computer Science Review, 37:100253, 2020.
  * [2] B. Bergougnoux, S. Høgemo, J. Telle, and M. Vatshelle.  Recognition of linear and star variants of leaf powers is in p.  In Michael A. Bekos and Michael Kaufmann, editors, Graph-Theoretic Concepts in Computer Science, pages 70–83, Cham, 2022. Springer International Publishing.
  * [3] A. Brandstädt, V. Le, and R. Sritharan.  Structure and linear-time recognition of 4-leaf powers.  ACM Trans. Algorithms, 5(1), 12 2008.
  * [4] A. Brandstädt, C. Hundt, F. Mancini, and P. Wagner.  Rooted directed path graphs are leaf powers.  Discrete Mathematics, 310(4):897–910, 2010.
  * [5] A. Brandstädt and V. Le.  Structure and linear time recognition of 3-leaf powers.  Information Processing Letters, 98(4):133–138, 2006.
  * [6] A. Brandstädt, V. Le, and D. Rautenbach.  A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers.  Discrete Mathematics, 309(12):3843–3852, 2009.
  * [7] P. Buneman.  A note on the metric properties of trees.  Journal of Combinatorial Theory, Series B, 17(1):48–50, 1974.
  * [8] H-C. Chang, R. Krauthgamer, and Z. Tan.  Almost-linear $\varepsilon$-emulators for planar graphs.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1311–1324, 2022.
  * [9] M-S. Chang and M-T. Ko.  The 3-steiner root problem.  In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science, pages 109–120, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
  * [10] V. Cohen-Addad, A. Filtser, P. Klein, and H. Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 589–600. IEEE, 2020.
  * [11] M. Dom, J. Guo, F. Hüffner, and R. Niedermeier.  Error compensation in leaf root problems.  pages 389–401, 12 2004.
  * [12] G. Ducoffe.  The 4-steiner root problem.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 14–26. Springer, 2019.
  * [13] G. Durán, F. Slezak, L. Grippo, F. Oliveira, and J. Szwarcfiter.  On unit interval graphs with integer endpoints.  Electronic Notes in Discrete Mathematics, 50:445–450, 2015.
  * [14] A. Filtser, M. Kapralov, and N. Nouri.  Graph spanners by sketching in dynamic streams and the simultaneous communication model.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1894–1913. SIAM, 2021.
  * [15] M. Hellmuth, C. Seemann, and P. Stadler.  Generalized fitch graphs ii: Sets of binary relations that are explained by edge-labeled trees.  Discrete Applied Mathematics, 283:495–511, 2020.
  * [16] S. Høgemo.  Lower bounds for leaf rank of leaf powers.  CoRR, abs/2402.18245, 2024.
  * [17] M. Lafond.  On strongly chordal graphs that are not leaf powers.  In H. Bodlaender and G. Woeginger, editors, Graph-Theoretic Concepts in Computer Science, pages 386–398, Cham, 2017. Springer International Publishing.
  * [18] M. Lafond.  Recognizing $k$-leaf powers in polynomial time, for constant $k$.  ACM Trans. Algorithms, 19(4), 9 2023.
  * [19] M. Lafond and N. El-Mabrouk.  Orthology and paralogy constraints: satisfiability and consistency.  BMC genomics, 15:1–10, 2014.
  * [20] H. Le and S. Solomon.  Near-optimal spanners for general graphs in (nearly) linear time.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3332–3361. SIAM, 2022.
  * [21] V. Le and C. Rosenke.  Computing optimal leaf roots of chordal cographs in linear time.  In International Symposium on Fundamentals of Computation Theory, pages 348–362. Springer, 2023.
  * [22] C. Lekkerkerker and J Boland.  Representation of a finite graph by a set of intervals on the real line.  Fundamenta Mathematicae, 51:45–64, 1962.
  * [23] Y. Long and P. Stadler.  Exact-2-relation graphs.  Discrete Applied Mathematics, 285:212–226, 2020.
  * [24] R. Nevries and C. Rosenke.  Towards a characterization of leaf powers by clique arrangements.  Graphs and Combinatorics, 32:2053–2077, 2016.
  * [25] N. Nishimura, P Ragde, and D. Thilikos.  On graph powers for leaf-labeled trees.  Journal of Algorithms, 42(1):69–108, 2002.
  * [26] A. Raychaudhuri.  On powers of strongly chordal and circular arc graphs.  Ars Combin., 34:147–160, 1992.
  * [27] M. Thorup and U. Zwick.  Spanners and emulators with sublinear distance errors.  In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 802–809, 2006.
  * [28] J. Van Den Brand, S. Forster, and Y. Nazari.  Fast deterministic fully dynamic distance approximation.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1011–1022. IEEE, 2022.
  * [29] P. Wagner and A. Brandstädt.  The complete inclusion structure of leaf power classes.  Theoretical Computer Science, 410(52):5505–5514, 2009.  Combinatorial Optimization and Applications.