A Note on Graphs with Largest Total \(k\)-Domination Number

Abstract

Let \(k \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(S\) of vertices in a graph is a total \(k\)-dominating set if every vertex of \(G\) is within distance at most \(k\) from some vertex of \(S\) other than itself. The smallest cardinality of such a set of vertices is called the total \(k\)-domination number of the graph and is denoted by \(\gamma_k^t(G)\). It is well known that \(\gamma_k^t(G) \leq \frac{2p}{2k+1}\) for \(p \leq 2k + 1\). In this paper, we present a characterization of connected graphs that achieve the upper bound. Furthermore, we characterize the connected graph \(G\) with \(\gamma_k^t(G) + \gamma_k^t(\overline{G}) = \frac{2p}{2k+1} + 2\).