Total $\{k\}$-domination in caterpillars: Structural properties and exact results
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.27181
curl -X POST /api/v1/records/arxiv/2610.27181/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.27181/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'