
The Library
Large-girth roots of graphs
Tools
Adamaszek, Anna and Adamaszek, Michał (2010) Large-girth roots of graphs. SIAM Journal on Discrete Mathematics, Vol.24 (No.4). pp. 1501-1514. doi:10.1137/100792949 ISSN 0895-4801.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/100792949
Abstract
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 vertical bar 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 Levenshtein [Discrete Math., 308 (2008), pp. 993-998] 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0895-4801 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.24 | ||||
Number: | No.4 | ||||
Number of Pages: | 14 | ||||
Page Range: | pp. 1501-1514 | ||||
DOI: | 10.1137/100792949 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | Centre for Discrete Mathematics and its Applications (DIMAP), EPSRC | ||||
Grant number: | EP/D063191/1 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |