×

Large-girth roots of graphs. (English) Zbl 1221.05101

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.

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

Citations:

Zbl 1142.05056
PDFBibTeX XMLCite
Full Text: DOI