H-domination in graphs Original Research Article

Let H be some fixed graph of order p. For a given graph G and vertex set S⊆V(G), we say that S is H-decomposable if S can be partitioned as S=S1∪S2∪⋯∪Sj where, for each of the disjoint subsets Si, with 1⩽i⩽j, we have |Si|=p and H is a spanning subgraph of 〈Si〉, the subgraph induced by Si. We define the H-domination number of G, denoted as γH(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write γH(G)=∞. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for γH(G). We show, in particular, that if δ(G)⩾2, then γP3(G)⩽3γ(G). Also, if γP3(G)=3γ(G), then every γ(G)-set is an efficient dominating set.