language: en

Powers of Trees

Paul E. Kearney and Derek G. Corneil
Department of Computer Science, University of Toronto,
Toronto ON, CANADA M5S 1A4
kearney@cs.toronto.edu dgc@cs.toronto.edu

Abstract. We present the first polynomial algorithm for recognizing tree powers. A graph G is a tree power if there is a tree T and a positive integer k such that T k ~ = G where x and are adjacent in T k if and only if d T (x; ) k. We also show that a natural extension of tree power recognition is NP-complete, namely, given a graph G and a positive integer r, determine if there is a tree power within r edges of G.

1 Introduction