On the existence of total dominating subgraphs with a prescribed additive hereditary property

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

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (596Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (135Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-608
Depositing User: Oliver Schaudt
Date Deposited: 12 Jul 2011 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/608