An Upper Bound for the Total Restrained Domination Number of Graphs

Abstract

Let G be a graph with vertex set V. A set D ⊆ V is a total restrained dominating set of G if every vertex in V has a neighbor in D and every vertex in V \ D has a neighbor in V \ D. The minimum cardinality of a total restrained dominating set of G is called the total restrained domination number of G, and is denoted by γtr (G). In this paper, we prove that if G is a connected graph of order n ≥ 4 and minimum degree at least two, then γtr(G) ≤ n-3√n/4. © 2012 Springer.