Abstract:
|
We extend the well-studied concept of a graph power to that
of a k-leaf power G of a tree T: G is formed by creating a node for each
leaf in the tree and an edge between a pair of nodes if and only if the
associated leaves are connected by a path of length at most k. By
discovering hidden combinatorial structure of cliques and
neighbourhoods,
we have developed polynomial-time algorithms that, for k=3 and k=4,
identify whether or not a given graph G is a k-leaf power of a tree T,
and if so, produce a tree T for which G is a k-leaf power. We believe
that our structural results will form the basis of a solution for more
general k. The general problem of inferring hidden tree structure on
the basis of leaf relationships shows up in several areas of
application. |