Skip to main content

Research Repository

Advanced Search

Computing square roots of graphs with low maximum degree

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

Computing square roots of graphs with low maximum degree Thumbnail


Authors

M. Cochefert

J-F. Couturier

P.A. Golovach

D. Kratsch

A. Stewart



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 Mar 29, 2024
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

Files





You might also like



Downloadable Citations