On the k-Total Domination Number of Circulant, Shadow, and Strong Product Graphs

Abstract

A set <inline-formula> <tex-math notation="LaTeX">$S\subseteq V(G)$ </tex-math></inline-formula> is called a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating set of a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> if every vertex of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> lies within distance at most <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> of some other vertex in <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$k\ge 1$ </tex-math></inline-formula>. The minimum cardinality of such a set is called the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, denoted by <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula>. In this paper, we investigate <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination from a coverage-based perspective. We establish a new lower bound for <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula> in terms of the diameter of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. To analyze neighborhood coverage in <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination, we extend the concepts of shadow and share to <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and introduce the neighborhood coverage number. We also extend the concept of redundant domination to the setting of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods. Together, these concepts quantify both the coverage provided by <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and the overlap among them. These concepts yield new insights into the structure of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating sets and are applied to obtain results for circulant graphs. We show that the shadow graph operation preserves the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number; that is, <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(D_{2}(G))=\gamma _{t,k}(G)$ </tex-math></inline-formula> for every graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. For strong product graphs, we establish general upper bounds and prove that <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(H\boxtimes H')=\gamma _{t,k}(H)$ </tex-math></inline-formula> whenever <inline-formula> <tex-math notation="LaTeX">$r(H')\le k$ </tex-math></inline-formula>. As a consequence, we obtain exact values of the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number for several classes of shadow and strong product graphs, including shadow graphs of paths and cycles, and strong products of paths and cycles.