Restricted Total Domination in Graphs with Minimum Degree Two

Abstract

The \(k\)-restricted total domination number of a graph \(G\) is the smallest integer \(t_k\), such that given any subset \(U\) of \(k\) vertices of \(G\), there exists a total dominating set of \(G\) of cardinality at most \(t\), containing \(U\). Hence, the \(k\)-restricted total domination number of a graph \(G\) measures how many vertices are necessary to totally dominate a graph if an arbitrary set of \(k\) vertices are specified to be in the set. When \(k = 0\), the \(k\)-restricted total domination number is the total domination number. For \(1 \leq k \leq n\), we show that \(t_k \leq 4(n + k)/7\) for all connected graphs of order \(n\) and minimum degree at least two and we characterize the graphs achieving equality. These results extend earlier results of the author (J. Graph Theory \(35 (2000), 21-45)\). Using these results we show that if \(G\) is a connected graph of order \(n\) with the sum of the degrees of any two adjacent vertices at least four, then \(\gamma_t(G) \leq 4n/7\) unless \(G \in \{C_3, C_5, C_6, C_{10}\}\).