A characterization of line graphs that are squares of graphs
The square of a graph G G , denoted by G2 G 2 , is the graph obtained from G G by putting an edge between two distinct vertices whenever their distance in G G is at most 2 2 . 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.
line graph the square of a graph linear time algorithm