k-tuple restrained domination in graphs

Abstract

For k ≥ 1 an integer, a set S of vertices in a graph G with minimum degree at least k − 1 is a k-tuple dominating set of G if every vertex of S is adjacent to at least k − 1 vertices in S and every vertex of V (G) / S is adjacent to at least k vertices in S; that is, |NG[v] ∩ S| ≥ k for every vertex v of G where NG[v] denotes the closed neighborhood of v which consists of v and all neighbors of v. A k-tuple restrained dominating set of G is a k-tuple dominating set S of G with the additional property that every vertex outside S has at least k neighbors outside S. The mini- mum cardinality of a k-tuple restrained dominating set of G is the k-tuple restrained domination number of G. When k = 1, the k-tuple restrained domination number is the well-studied restrained domination number. In this paper, we determine the k-tuple restrained domination number of several classes of graphs. Tight bounds on the k-tuple restrained domination number of a general graph are established. We present basic properties of the k-tuple restrained domatic number of a graph which is the maximum number of the classes of a partition of V (G) into k-tuple restrained dominating sets of G.