$k$-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for $𝒌\mathbf{\ge }\mathrm{𝟓}$

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 ${\mathrm{dist}}_{H_n}(b,t)\ge 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 1(b).

The left tree in Figure 1(b) is obtained by merging $T_{\text{Top}}$ with $n$ copies of $T_I$, denoted as $T_I^1,\mathrm{\dots },T_I^n$. We identify $t$ with $t_I^1$, and we identify the parent of $t$ in $T_{\text{Top}}$ with the parent of $t_I^1$ in $T_I^1$. Similarly, for all $j\le 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{Bot}$. 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_I^1$ then, using Lemma 3, we conclude $d(v_1,t)\ge m_{T_{\text{Top}}}(t)=3$. Furthermore, using the second point of Lemma 5, we conclude $d(v_2,t_I^1)\ge m_{T_I}(t_I)=k$. Therefore, $d(v_1,v_2)\ge d(v_1,t)+d(v_2,t_I^1)-2\ge 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\le 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)\ge 3$ and $d(v_2,t_I^{j+1})\ge k$. Thus, $d(v_1,v_2)\ge d(v_1,b_I^j)+d(v_2,t_I^{j+1})-2\ge 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 1(b) is formed by merging $n$ copies of $R_I$, denoted $R_I^1,\mathrm{\dots },R_I^n$, with $T_{\text{Bot}}$. For all $j\le 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_I^n$ 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_I^j$ different from $b_I^j$ for some $j\le n-1$ and $v_2$ is a leaf of $R_I^{j+1}$ different from $t_I^{j+1}$ then, using Lemma 5, we conclude $d(v_1,b_I^j)\ge m_{R_I}(b_I)=4$ and $d(v_2,t_I^{j+1})\ge m_{R_I}(t_I)=k-1$. Thus, $d(v_1,v_2)\ge d(v_1,b_I^j)+d(v_2,t_I^{j+1})-2\ge 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_I^n$ 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)\ge 4$ and, using Lemma 4, $d(v_2,b)\ge k-1$. Therefore $d(v_1,v_2)\ge d(v_1,b_I^n)+d(v_2,b)-2\ge 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 3. Turning to the induction step, assume that the property holds for some $n\ge 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)\le k-1$ . This assumption would imply that $d(v_1,v_2)\le d(v_1,b_I^n)+d(v_2,b_I^n)-2\le 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 5, which concludes the induction.

Now assume by contradiction that there exists a $k$-leaf root $T$ of $H_n$. Then $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 4 implies that there exists a vertex $v_2$ in Bot, distinct from $b$, such that $d(v_2,b)\le k-1$. Combining these equations, we get $d(v_1,v_2)\le 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.

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 6, $H_n$ is strongly chordal. By definition, $G_{k,n}$ is not in $ℒ(k)$, but every induced subgraph $G$ of $G_{k,n}$ is in $ℒ(k)$ if $G\ne G_{k,n}$. It remains to prove that $|G_{k,n}|\ge n$. By Lemma 6, both $H_n-\text{Bot}$ and $H_n-\text{Top}$ are in $ℒ(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 6, ${\mathrm{dist}}_{H_n}(b,t)\ge n$, and therefore $|G_{k,n}|\ge n$. $◀$

Our main result follows directly from Lemma 7

If $ℒ(k)$ is the set of strongly chordal graphs which are ${ℱ}_k$-free, then ${ℱ}_k$ must contain $G_{k,n}$ for all $n$ because it is strongly chordal and a minimal non $k$-leaf power by Lemma 7. But the set $\{G_{k,n},n\ge 0\}$ is infinite because $G_{k,n}$ has more than $n$ vertices. Therefore ${ℱ}_k$ must be infinite, which concludes the proof of Theorem 1. $◀$

Let $P$ be the path on the $2k-3$ vertices $v_1,\mathrm{\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 2, 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 [32], which states that if $P^{k-2}$ is an induced subgraph of $T^k$, where $T$ is a tree and $k\ge 1$, then $d_T(v_{k-3},v_{k-2})\le 3$ (note that the lemma is more general, as $P$ can have length $2p+1$ for any $p\ge 2$, and the result applies to $P^p$ and $d_T(v_{p-1},v_p)\le k-p+1$; here we took $p=k-2$). Thus, if $T$ is any $k$-leaf root of Top, then $T^k$ does contain $P^{k-2}$ as an induced subgraph and the property holds. $◀$

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:

This implies that $d(v_1,v_2)+d(v_3,b)\le 2k$ and $d(v_2,v_3)+d(b,v_1)\le 2k$.

So, $d(v_1,v_3)+d(b,v_2)>\max \{d(v_1,v_2)+d(v_3,b),d(v_2,v_3)+d(b,v_1)\}$ which contradicts Theorem 8 $◀$

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

See 4

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 9, $d(b,v_2)\le k-1$ in any leaf root. Thus the first property holds. For the second property, there are two cases, illustrated in Figure 3, depending upon the parity of $k$.

• $\mathrm{■}$

  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.

• $\mathrm{■}$

  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. $◀$

Assume that $d(t,x_1)+d(x_2,x_3)\ge \max \{d(t,x_2)+d(x_1,x_3),d(t,x_3)+d(x_1,x_2)\}$. Then, by using this assumption and our bound on $d(t,x_1)$, we get:

Then, by combining this bound with our bound on $d(y,x_1)$, we get:

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

Now, assume without loss of generality that $d(t,x_2)+d(x_1,x_3)\ge d(t,x_3)+d(x_1,x_2)$. Then, by Theorem 8, we must have:

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)\le 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:

This completes the proof. $◀$

We will also use the following simple lemma:

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 5

Before proving this lemma, let’s discuss the requirement that $k\ge 5$. First observe that no such graph can exist for $k\le 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.

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\ge 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\ge 5$ we must have $q\ge 2$.

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

• $\mathrm{■}$

  $t$ and $b$

• $\mathrm{■}$

  $X=\{x_1,\mathrm{\dots },x_q\}$

• $\mathrm{■}$

  $Y=\{y_2,\mathrm{\dots },y_q\}$

The edge set is defined as follows (note that for clarity, we use ordered pairs to represent edges, with the understanding that the edges are undirected):

• $\mathrm{■}$

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

• $\mathrm{■}$

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

• $\mathrm{■}$

  For $i=2\mathrm{\dots }q$, for $j=i\mathrm{\dots }q$, $(y_i,x_j)$ is an edge.

• $\mathrm{■}$

  $(b,y_q)$ is an edge.

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

• $\mathrm{■}$

  $t$ is adjacent to $X=\{x_1,\mathrm{\dots },x_q\}$.

• $\mathrm{■}$

  $b$ is adjacent to $X$ and to $y_q$.

• $\mathrm{■}$

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

• $\mathrm{■}$

  For $i=2,\mathrm{\dots },q$, for $j=i,\mathrm{\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:

This construction is illustrated in Figure 4. We remark that this construction only makes sense for $k\ge 5$ because if $k=3$ or $k=1$ then $Y$ is an empty set.

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

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 11 with $t$, $x_i$ and $x_j$, $d(x_i,x_j)$ must be even (and, thus, at most $k-1$).

Assume . Then $d(t,x_i)=k=\min \{d(t,x_j),d(t,x_{\mathrm{\ell }})\}$. Furthermore, $d(y_j,x_i)>k\ge \max \{d(y_j,x_j),d(y_j,x_{\mathrm{\ell }})\}$ because $y_j$ is adjacent to $x_j$ and $x_{\mathrm{\ell }}$ but not $x_i$ (nor $t$). So, by Lemma 10, we get:

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

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})=\mathrm{\cdots }=d(x_i,x_q)={\lambda }_i$. Moreover, as shown, the ${\lambda }_i$ must be even. Thus $k-1\ge {\lambda }_1>\mathrm{\cdots }>{\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 .

Recall $d(t,x_i)=k=\min \{d(t,x_q),d(t,b)\}$ and $d(y_q,x_i)>k\ge \max \{d(y_q,x_q),d(y_q,b)\}$, for . So, by Lemma 10, we obtain:

Consider $i=1$. Recall $k\ge 5$ and $q\ge 2$. So $q\ne 1$ implying that $x_q\ne x_1$. It follows that

However, we must have $d(t,b)>k$ and $d(x_1,b)\le k$. So it must be that $d(t,b)=k+1$ and $d(x_1,b)=k$.

Next consider $i=q-1$. Because $q\ge 2$, we have $i\ge 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\le i\le q$, we have

Finally, recall that . This implies that . In particular, . Moreover, by Lemma 11, 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. $\mathrm{⊲}$

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,\mathrm{\dots },q+1$.

3. 3.

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

4. 4.

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

5. 5.

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