Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs

Van Bang Le, Andrea Oversberg, Oliver Schaudt

The square of a graph $G$, denoted $G^2$, is obtained from $G$ by putting an edge between two distinct vertices whenever their distance is two. Then $G$ is called a square root of…