Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.