ALGORITHMS FOR SQUARE ROOTS OF GRAPHS

The nth power (n greater than or equal to 1) of a graph G = (V, E), written G(n), is defined to be the graph having V as its vertex set with two vertices u, v adjacent in G(n) if and only if there exists a path of length at most n between them. Similarly, graph H has an nth root G if G(n) = H. For the case of n = 2, G(2) is the square of G and G is the square root of G(2). 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.