The Library

Large-Girth Roots of Graphs

Tools

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.

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.

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
Identification Number: 10.1137/100792949
Status: Peer Reviewed
Publication Status: Published
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
Related URLs:
URI: http://wrap.warwick.ac.uk/id/eprint/47406

Request changes to a record

Actions (login required)

View Item View Item