Total restrained domination in graphs with minimum degree two

AbstractIn 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⧹S is adjacent to a vertex in V⧹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-Δ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-23Δ-293Δ-8-79 and that this bound is sharp