Algorithms for Square Roots of Graphs

The nth power( n ≥ 1) of a graph $G = ( V,E )$, written Gⁿ, is defined to be the graph having V as its vertex set with two vertices u, v adjacent in Gⁿ if and only if there exists a path of length at most n between them. Similarly, graph H has an nth rootG if Gⁿ = H. For the case of $n = 2$, G² is the square of G and G is the square root of G². This paper presents a linear time algorithm for finding the tree square roots of a given graph and a linear time algorithm for finding the square roots of planar graphs. A polynomial time algorithm for finding the square roots of subdivision graphs, which is equivalent to the problem of the inversion of total graphs, is also presented. Further, the authors give a linear time algorithm for finding a Hamiltonian cycle in a cubic graph and prove the NP-completeness of finding the maximum cliques in powers of graphs and the chordality of powers of trees.