Total restrained domination in graphs with minimum degree two

In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex is adjacent to a vertex in S and every vertex of V {minus 45 degree rule} S is adjacent to a vertex in V {minus 45 degree rule} S. The minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γ_tr (G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ ≤ n - 2. We prove that if n ≥ 4, then γ_tr (G) ≤ n - frac(Δ, 2) - 1 and this bound is sharp. If we restrict G to a bipartite graph with Δ ≥ 3, then we improve this bound by showing that γ_tr (G) ≤ n - frac(2, 3) Δ - frac(2, 9) sqrt(3 Δ - 8) - frac(7, 9) and that this bound is sharp.