Milanic, Martin ORCID: 0000-0002-8222-8097, Oversberg, Andrea and Schaudt, Oliver (2014). A characterization of line graphs that are squares of graphs. Discret Appl. Math., 173. S. 83 - 92. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6771
Full text not available from this repository.Abstract
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. (C) 2014 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||||||||||||||
Creators: |
|
||||||||||||||||
URN: | urn:nbn:de:hbz:38-431916 | ||||||||||||||||
DOI: | 10.1016/j.dam.2014.03.021 | ||||||||||||||||
Journal or Publication Title: | Discret Appl. Math. | ||||||||||||||||
Volume: | 173 | ||||||||||||||||
Page Range: | S. 83 - 92 | ||||||||||||||||
Date: | 2014 | ||||||||||||||||
Publisher: | ELSEVIER SCIENCE BV | ||||||||||||||||
Place of Publication: | AMSTERDAM | ||||||||||||||||
ISSN: | 1872-6771 | ||||||||||||||||
Language: | English | ||||||||||||||||
Faculty: | Unspecified | ||||||||||||||||
Divisions: | Unspecified | ||||||||||||||||
Subjects: | no entry | ||||||||||||||||
Uncontrolled Keywords: |
|
||||||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/43191 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |