Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs
The square of a graph , denoted , is obtained from by putting an edge between two distinct vertices whenever their distance is two. Then is called a square root of . Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph. We present a polynomial time algorithm that decides whether a given graph has a ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges. In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one.