On Graph Powers for Leaf-Labeled Trees

✍ Scribed by Naomi Nishimura; Prabhakar Ragde; Dimitrios M. Thilikos

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 256 KB
• Volume: 42
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1195

✦ Synopsis

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 neighborhoods, 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.