Universität zu Köln

Schaudt, Oliver (2012). On weighted efficient total domination. Journal of Discrete Algorithms, 10 (1). pp. 61-69. Elsevier.

Preview

PDF zaik2010-598.pdf - Submitted Version Download (148kB) | Preview

Abstract

An efficiently total dominating set of a graph G is a subset of its vertices, such that every 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 present two graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs and graphs which only induce cycles of length divisible by four. Furthermore, claw-free etd graphs are shown to be perfect.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549936
Journal or Publication Title:	Journal of Discrete Algorithms
Volume:	10
Number:	1
Page Range:	pp. 61-69
Date:	2012
Publisher:	Elsevier
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/54993