Skip to content
Preprint

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

Oct 2026 · 0 citations · 6 references
Mathematics

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 $\gamma^{\{k\}}_t(G) = k\gamma_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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.