Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time

Michel Habib, Thu-Hien To

A graph is a $k$-leaf power of a tree $T$ if its vertices are leaves of $T$ and two vertices are adjacent in $T$ if and only if their distance in $T$ is at most $k$. Then $T$ is a…