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

Given a graph class GG, 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 GG and (ii) whether G   has such a set of cardinality at most a given threshold. We give sufficient conditions on GG under which these two problems are NP-hard. This condition is fulfilled in a wide variety of classes of graphs.

► Existence of connected/total dominating subgraphs of given structure is NP-hard.
► For many structures, NP-hardness remains for K1,5K1,5-free instances.
► Minimum connected/total dominating subgraph with prescribed structure is NP-hard.
► For many structures, NP-hardness remains for bip. instances with max. degree 4.