Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418330 | Discrete Applied Mathematics | 2014 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Milanič, Andrea Oversberg, Oliver Schaudt,