On total restrained domination in graphs

Abstract

In this paper we initiate the study of total restrained domination in graphs. Let G = (V,E) be a graph. A total restrained dominating set is a set S $$ \subseteq $$ V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by γ (G), is the smallest cardinality of a total restrained dominating set of G. First, some exact values and sharp bounds for γ (G) are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for γ (G) is NP-complete even for bipartite and chordal graphs in Section 4.