Large-girth roots of graphs
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-4801Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/100792949
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|
|Number of Pages:||14|
|Page Range:||pp. 1501-1514|
|Access rights to Published version:||Restricted or Subscription Access|
|Funder:||Centre for Discrete Mathematics and its Applications (DIMAP), EPSRC|
Actions (login required)