The Library
Large-girth roots of graphs
Tools
Tools
Tools
Adamaszek, Anna and Adamaszek, Michał. (2010) Large-girth roots of graphs. SIAM Journal on Discrete Mathematics, Vol.24 (No.4). pp. 1501-1514. ISSN 0895-4801
Full text not available from this repository.
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 > Computer Science Faculty of Science > Mathematics |
| Journal or Publication Title: | SIAM Journal on Discrete Mathematics |
| Publisher: | Society for Industrial and Applied Mathematics |
| ISSN: | 0895-4801 |
| Official Date: | 2010 |
| Volume: | Vol.24 |
| Number: | No.4 |
| Number of Pages: | 14 |
| Page Range: | pp. 1501-1514 |
| Identification Number: | 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 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/4575 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
