An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some 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 γ _tr(G) of G. Jiang et al. (Graphs Combin 25:341-350, 2009) showed that if G is a connected cubic graph of order n, then γ _tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ _tr(G) ≤ (n + 4)/2. We provide two infinite families of connected cubic graphs G with γ _tr(G) = n/2, showing that our new improved bound is essentially best possible.