Skip to Main content Skip to Navigation
Conference papers

Large-girth roots of graphs

Abstract : We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3, thus improving a bound conjectured by Farzad et al. (STACS 2009). 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 towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for r=2,3.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Publications Loria <>
Submitted on : Monday, February 8, 2010 - 5:29:45 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:30 AM
Long-term archiving on: : Friday, June 18, 2010 - 7:36:30 PM


Files produced by the author(s)


  • HAL Id : inria-00454554, version 1



Anna Adamaszek, Michal Adamaszek. Large-girth roots of graphs. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.35-46. ⟨inria-00454554⟩



Record views


Files downloads