A characterization of line graphs that are squares of graphs

The square of a graph GG, denoted by G2G2, is the graph obtained from GG by putting an edge between two distinct vertices whenever their distance in GG is at most 22. Motwani and Sudan proved that it is NP-complete to decide whether a given graph is the square of some graph. In this paper we give a characterization of line graphs that are squares of graphs, and show that if a line graph is a square, then it is a square of a bipartite graph. As a consequence, we obtain a linear time algorithm for deciding whether a given line graph is the square of some graph.