Adamaszek, Anna; Adamaszek, Michał Large-girth roots of graphs. (English) Zbl 1221.05101 SIAM J. Discrete Math. 24, No. 4, 1501-1514 (2010). Summary: We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm for \(r\)-th powers of graphs of girth at least \(2r+3\), thus improving a recently conjectured bound. Our algorithm also finds all \(r\)-th roots of a given graph that have girth at least \(2r+3\) and no degree one vertices, which is a step toward a recent conjecture of V. I. Levenshtein [“A conjecture on the reconstruction of graphs from metric balls of their vertices,” Discrete Math. 308, No.5–6, 993–998 (2008; Zbl 1142.05056)] that such roots should be unique. Similar algorithms have so far been designed only for \(r=2,3\). On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller. Cited in 4 Documents MSC: 05C12 Distance in graphs 05C75 Structural characterization of families of graphs 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:graph roots; graph powers; complexity; recognition algorithms Citations:Zbl 1142.05056 PDFBibTeX XMLCite \textit{A. Adamaszek} and \textit{M. Adamaszek}, SIAM J. Discrete Math. 24, No. 4, 1501--1514 (2010; Zbl 1221.05101) Full Text: DOI