On tree roots of graphs

Abstract

A graphG′=(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 and V′=V·G′is denoted by Gⁿ . G 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≇K_p , since in that case it is the nth power of all trees with same number of vertices and diameter d≥n (Hence in some of the lemmas it is assumed that d(T)>n).

Keywords:

• Power of a Graph
• Root of a Graph

C.R. Categories:

• F 2.2
• G 2.2