Exact leaf powers

AbstractWe define and study the new notion of exact k-leaf powers where a graph G=(VG,EG) is an exact k-leaf power if and only if there exists a tree T=(VT,ET) — an exact k-leaf root of G — whose set of leaves equals VG such that uv∈EG holds for u,v∈VG if and only if the distance of u and v in T is exactly k. This new notion is closely related to but different from leaf powers and neighbourhood subtree tolerance graphs.We prove characterizations of exact 3- and 4-leaf powers which imply that such graphs can be recognized in linear time and that also the corresponding exact leaf roots can be found in linear time. Furthermore, we characterize all exact 5-leaf roots of chordless cycles and derive several properties of exact 5-leaf powers