The complexity of connected domination and total domination by restricted induced graphs
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.
|Depositing User:||Oliver Schaudt|
|Date Deposited:||12 Apr 2011 00:00|
|Last Modified:||09 Jan 2012 14:36|