On tree roots of graphs

A graph G ′ = (V,E′) is defined to be the nth power of a graph G = (V,E) if E ′ = {{x, y} | d(x, y) ≤ n in G}. G is said to be an nth root of G′. Every graph G has a unique nth power for all n ≥ 1, but a graph may have zero or more nth roots. In this paper, we endeavour to devise an algorithm to determine whether a graph is some power of a tree T. Also, we assume that the given graph G 6 = Kp, since in that case it is the nth power of all trees with same number of vertices and diameter d ≤ n/2. Moreover, some of the lemmas assume that d(G)> n. Keywords: Power of a graph, roots of a graph, powers of trees 1 Concepts, terms and definitions We define below some terms which are used later in the paper. Graph theoretic definitions not given here are used in the sense of Harary[1]. Some more definitions and concepts will be introduced when required. Definitions-End-deleted tree- The end deleted tree T ′ of a given tree T is defined to be the tree obtained by deletion of the leaf nodes of T. In the trivial case when T is a single node or K2, T ′ is defined to be an empty graph. ith order leaf nodes- The set of ith order leaf nodes Li is defined to be that set of vertices which are leaf nodes of i-times end deleted tree of T. i.e., a vertex v ∈ Li if v is a leaf node in i-times end deleted tree. In the base case, L0 is the set of leaf nodes of T