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. Published in: Leibniz International Proceedings in Informatics (LIPIcs), Volume 5 pp. 35-46. ISBN 9783939897163. doi:10.1137/100792949 ISSN 1868-8969.
|
PDF
WRAP_Adamaszek_1001.AdamaszekAnna.2442.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution No Derivatives. Download (450Kb) | Preview |
|
PDF
adamaszek.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (237Kb) |
Official URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2442
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 | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||
ISBN: | 9783939897163 | ||||
ISSN: | 1868-8969 | ||||
Official Date: | 8 February 2010 | ||||
Dates: |
|
||||
Volume: | Volume 5 | ||||
Page Range: | pp. 35-46 | ||||
DOI: | 10.1137/100792949 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 21 December 2015 | ||||
Date of first compliant Open Access: | 21 December 2015 | ||||
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 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year