Universität zu Köln

Schaudt, Oliver (2015). On disjoint maximal independent sets in graphs. Inf. Process. Lett., 115 (1). S. 23 - 28. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6119

Full text not available from this repository.

Abstract

An old problem in graph theory is to characterize the graphs that admit two disjoint maximal independent sets. In this paper, we characterize the class of graphs for which every induced subgraph admits two disjoint maximal independent sets. Moreover, we state a polynomial-time algorithm which, for an arbitrary input graph G, either constructs two disjoint maximal independent sets or puts out an induced subgraph of G from the list of forbidden induced subgraphs. As a second result, we show the following: the computation of two disjoint maximal independent sets of minimum total size, NP-hard for general graphs, can be done in linear time on trees. (C) 2014 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-419848
DOI:	10.1016/j.ipl.2014.08.010
Journal or Publication Title:	Inf. Process. Lett.
Volume:	115
Number:	1
Page Range:	S. 23 - 28
Date:	2015
Publisher:	ELSEVIER SCIENCE BV
Place of Publication:	AMSTERDAM
ISSN:	1872-6119
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language DOMINATING SETS Multiple languages Computer Science, Information Systems Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/41984