On equality in an upper bound for the restrained and total domination numbers of a graph (Q2461210)

Let \(G = (V,E)\) be a graph. A set \(S \subset V\) is a restrained dominating set (RDS) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \;S\). The restrained dominating number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of an RDS of \(G\). A set \(S \subset V\) is a total dominating set (TDS) if every vertex in \(V\) is adjacent to a vertex in \(S\). The total domination number of a graph \(G\) without isolated vertices, denoted by \(\gamma_t(G)\), is the minimum cardinality of a TDS of \(G\). Let \(\delta\) and \(\Delta\) denote the minimum and maximum degrees, respectively, in \(G\). If \(G\) is a graph of order \(n\) with \(\delta \geq 2\), then it is shown that \(\gamma_r(G) \leq n - \Delta\), and we characterize the connected graphs \(\delta \geq 2\) achieving this bound that have no 3-cycle as well as those connected graphs with \(\delta \geq 2\) that have neither a 3-cycle nor a 5-cycle. \textit{E. J. Cockayne, R. M. Dawes} and \textit{S. T. Hedetuiemi} [Total domination in graphs, Networks 10, 211--219 (1980; Zbl 0447.05039)] showed that if \(G\) is a connected graph of order \(n \geq 3\) and \(\Delta \leq n-2\), then \(\gamma_t(G) \leq n - \Delta\). We further characterize the connected graphs \(G\) of order \(n \geq 3\) with \(\Delta \leq n-2\) that have no 3-cycle and achieve \(\gamma_t(G) = n - \Delta\).