Computing square roots of trivially perfect and threshold graphs
A graph H H is a square root of a graph G G if two vertices are adjacent in G G if and only if they are at distance one or two in H H . Computing a square root of a given graph is NP-hard, even when the input graph is restricted to be chordal. In this paper, we show that computing a square root can be done in linear time for a well-known subclass of chordal graphs, the class of trivially perfect graphs. This result is obtained by developing a structural characterization of graphs that have a split square root. We also develop linear time algorithms for determining whether a threshold graph given either by a degree sequence or by a separating structure has a square root.
threshold graph square root of a graph chordal graph trivially perfect graph linear time algorithm square of a graph split graph