Large-Girth Roots of Graphs
Adamaszek, Anna and Adamaszek, Michał (2010) Large-Girth Roots of Graphs. In: 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Nancy, France, 1-8 Feb 2010 pp. 35-46.Full text not available from this repository.
Official URL: http://hal.inria.fr/docs/00/45/45/54/PDF/adamaszek...
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.
|Item Type:||Conference Item (Paper)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Computer Science|
|Date:||1 February 2010|
|Page Range:||pp. 35-46|
|Conference Paper Type:||Paper|
|Title of Event:||27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010|
|Type of Event:||Conference|
|Location of Event:||Nancy, France|
|Date(s) of Event:||1-8 Feb 2010|
Actions (login required)