Universität zu Köln

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:	Creators Email ORCID ORCID Put Code Milanic, Martin UNSPECIFIED orcid.org/0000-0002-8222-8097 UNSPECIFIED Oversberg, Andrea UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
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:	Keywords Language ROOTS Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/43191