2016/03/08 by Henning, M. A., Kazemi, Adel P.
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1603.02433
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 minimum 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 upper 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.