| Popis: |
The square of a graph G , denoted by G 2 , is the graph obtained from G by putting an edge between two distinct vertices whenever their distance in G is at most 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. |
Full Text from ScienceDirect