Universität zu Köln

Schaudt, Oliver (2011). On the existence of total dominating subgraphs with a prescribed additive hereditary property. Discrete Mathematics, 311 (18-19). pp. 2095-2101. Elsevier Science.

Preview

PDF zaik2010-608.pdf - Submitted Version Download (138kB) | Preview

Abstract

Recently, Bacsô and Tuza gave a full characterization of the graphs for which every connected induced subgraph has a connected dominating subgraph satisfying an arbitrary prescribed hereditary property. Using their result, we derive a similar characterization of the graphs for which any isolate-free induced subgraph has a total dominating subgraph that satisfies a prescribed additive hereditary property. In particular, we give a characterization for the case where the total dominating subgraphs are disjoint union of complete graphs. This yields a characterization of the graphs for which every isolate-free induced subgraph has a vertex-dominating induced matching, a so-called induced paired-dominating set.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550029
Journal or Publication Title:	Discrete Mathematics
Volume:	311
Number:	18-19
Page Range:	pp. 2095-2101
Date:	2011
Publisher:	Elsevier Science
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/55002