Total $\{k\}$-domination in caterpillars: Structural properties and exact results

Source abstract

The total $\{k\}$-domination problem ($T\{k\}DP$) seeks a minimum-weight function such that the sum of weights in every open neighborhood is at least $k$. While this problem is known to be NP-hard for general graphs, we demonstrate that for the family of caterpillars, it simplifies to the classical total domination number ($k=1$) via the identity $γ^{\{k\}}_t(G) = kγ_t(G)$. This reduction is supported by a general upper bound established for all graphs, which we prove to be tight specifically for caterpillars. The central tool for our analysis is the introduction of a $(T,R)$-representation, a one-to-one mapping that abstracts caterpillar structure into discrete vectors based on support vertex distribution and central path segment lengths. By characterizing these segments through congruence modulo 4, we derive an exact closed-form expression for the total $\{k\}$-domination number of any caterpillar graph.