H-domination in graphs

Abstract

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. © 2003 Published by Elsevier B.V.