Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 20 min ago
PreprintCC BY 4.0arXiv

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

  • Mariana Escalante
  • Paola Tolomei
  • María Inés Lopez Pujato
Open at sourcePDFDOICite

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.

Related

  1. Domination and Total Domination in Johnson graphs
    María Gracia Cornet, Tanja Dravec, Pablo Torres
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On graphs with equal domination and total domination numbers
    Sudip Bera
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Settling the total domination-annihilation conjecture for graphs with minimum degree two
    Marko Jakovac
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Grundy Total Domination and Skew Zero Forcing in Cartesian Products of Paths and Cycles
    Fei-Huang Chang
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Structural aspects of $1$-limited domination in cubic graphs
    Goran Radić, Gordana Radić, Aleksandra Tepeh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{escalante2026total,
  title = {{Total $\k\$-domination in caterpillars: Structural properties and exact results}},
  author = {Mariana Escalante and Paola Tolomei and María Inés Lopez Pujato},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27181},
  eprint = {2610.27181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27181},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Total {k}-domination in caterpillars: Structural properties and exact results
AU  - Mariana Escalante
AU  - Paola Tolomei
AU  - María Inés Lopez Pujato
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.27181
UR  - https://arxiv.org/abs/2610.27181
AB  - 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.
ER  -