Graphs with large total restrained domination number

Abstract

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G 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 minimum cardinality of a TRDS of G. In this paper we characterize the trees T of order n with γ_tr(T) = n and γ_tr(T) = n - 2, respectively. For general graphs, we also characterize the graphs G of order n with γ_tr(G) = n.