Uniqueness of graph square roots of girth six (Q551233)

Summary: We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of \textit{B. Farzad, L. C. Lau, V. B. Le} and \textit{N. N. Tuy} [``Computing graph roots without short cycles,'' Proc. 26th. STACS 2009, pp. 397--408 (2009)] on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers.