Cochefert, M. and Couturier, J-F. and Golovach, P.A. and Kratsch, D. and Paulusma, D. and Stewart, A. (2018) 'Computing square roots of graphs with low maximum degree.', Discrete applied mathematics., 248 . pp. 93-101.
A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (408Kb)
|Publisher Web site:||https://doi.org/10.1016/j.dam.2017.04.041|
|Publisher statement:||© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||02 May 2017|
|Date deposited:||23 May 2017|
|Date of first online publication:||22 May 2017|
|Date first made open access:||22 May 2018|
Save or Share this output
|Look up in GoogleScholar|