The complexity of connected domination and total domination by restricted induced graphs

Schaudt, Oliver and Schrader, Rainer (2010) The complexity of connected domination and total domination by restricted induced graphs.
Technical Report , 8 p.

Abstract

Given a graph class C, it is natural to ask whether a given graph has a connected or a total dominating set inducing a graph of C and, if so, what is the minimal size of such a set. We give a sufficient condition on C for the intractability of this problem. This condition is fulfilled by a wide range of graph classes.


Actions:
Download: [img] Postscript
Download (457Kb) | Preview
Download: [img] PDF
Download (203Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-606
Depositing User: Oliver Schaudt
Date Deposited: 12 Apr 2011 00:00
Last Modified: 09 Jan 2012 14:36
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/606