The complexity of connected dominating sets and total dominating sets with specified induced subgraphs

Given a graph class g, it is natural to ask (i) whether a given graph G has a connected or a total dominating set whose induced subgraph is a member of g and (ii) whether G has such a set of cardinality at most a given threshold. We give sufficient conditions on g under which these two problems are NP-hard. This condition is fulfilled in a wide variety of classes of graphs. (C) 2012 Elsevier B.V. All rights reserved