Computing square roots of graphs with low maximum degree

Cochefert, M.; Couturier, J-F.; Golovach, P.A.; Kratsch, D.; Paulusma, D.; Stewart, A.

Abstract

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.

Citation

Cochefert, M., Couturier, J., Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics, 248, 93-101. https://doi.org/10.1016/j.dam.2017.04.041

• Journal Article Type: Article
• Acceptance Date: May 2, 2017
• Online Publication Date: May 22, 2017
• Publication Date: Oct 31, 2018
• Deposit Date: May 20, 2017
• Publicly Available Date: May 22, 2018
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 248
• Pages: 93-101
• DOI: https://doi.org/10.1016/j.dam.2017.04.041
• Public URL: https://durham-repository.worktribe.com/output/1386597