The Square of a Tree

The correspondence between graphs, matrices and relations is well known and presents an interesting field of investigation. With any graph G there is associated a symmetric square matrix of O's and l's, called its "adjacency matrix". Forming the boolean square of this matrix, we may call the corresponding graph "the square of G". It is an open problem (communicated to us by N. J. Fine) to characterize those graphs that have at least one square root graph, and in general those graphs that have an nth root for any positive integer n. This paper presents a partial solution to the general problem by characterizing those graphs with a tree for a square root. It is also shown that, if the graphs obtained on squaring two trees are isomorphic, then the trees themselves are isomorphic. In the course of the development of this paper, an algorithm is given * Princeton University and Institute for Advanced Study (presently at University of Michigan); work supported by a grant from the Odioc of Naval Research to the Princeton University Logistics Project. 641