k-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5

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≤ 4, it is known that there exists a finite set Fₖ of graphs such that the class $L(k)$ of k-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in Fₖ as an induced subgraph. We prove no such characterization holds for k≥ 5. That is, for any k≥ 5, there is no finite set Fₖ of graphs such that $L(k)$ is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in Fₖ.