Recognition of Linear and Star Variants of Leaf Powers is in P

Benjamin Bergougnoux, Svein Høgemo, Jan Arne Telle +1

A $k$-leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$. A graph is a leaf p…