Recognizing k-leaf powers in polynomial time, for constant k

Manuel Lafond

A graph $G$ is a $k$-leaf power if there exists a tree $T$ whose leaf set is $V(G)$, and such that $uv\in E(G)$ if and only if the distance between $u$ and $v$ in $T$ is at most $…