Article ID Journal Published Year Pages File Type
418330 Discrete Applied Mathematics 2014 9 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,