Universität zu Köln

Schaudt, Oliver (2010). On efficient total domination. Working Paper.

Preview

PDF zaik2010-597.pdf Download (109kB) | Preview

Abstract

An efficiently total dominating set of a graph G is a subset of its vertices such that each vertex of G is adjacent to exactly one vertex of the subset. If there is such a subset, then G is an efficiently total dominatable graph (G is etd). We show that the corresponding etd decision problem is NP-complete on (1,2)-colorable chordal graphs and on planar bipartite graphs of maximum degree 3 and obtain polynomial solvability on T_3-free chordal graphs, implying polynomial solvability on interval graphs and circular arc graphs.

Item Type:	Monograph (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549921
Journal or Publication Title:	Information Processing Letters
Date:	2010
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54992