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

Introduction

Throughout this paper, we consider a (simple) graph $G$, with vertex set $V$ and edge set $E$. When we need to emphasize their relationship with the graph, we write $V(G)$ and $E(G)$. For each $v \in V$, $N_G(v) = \{u \in V : uv \in E\}$ denotes the (open) neighborhood of $v$ in the graph $G$, or simply $N(v)$ when the graph is clear from the context. Two vertices of $G$ are adjacent if there is an edge in $E$ having them as endpoints. The degree of a vertex $v$ is $d(v) = |N(v)|$. A vertex $v$ is isolated if $d(v) = 0$ and it is a leaf if $d(v) = 1$.

A (simple) path is a graph defined by a sequence of (distinct) adjacent vertices. Every vertex in a path has degree 2 except for the two terminal ones, which have degree 1.

For any $S \subseteq V$, the subgraph of $G$ induced by $S$ is the graph with vertex set $S$ such that two vertices of $S$ are adjacent if and only if they are adjacent in $G$.

A caterpillar is a connected graph with the property that after deleting the leaves, it results in a path, called the spine or central path of the caterpillar. In a caterpillar $G$, every vertex in the central path adjacent to a leaf is a support vertex.

Graph domination is a fundamental concept widely used to model a variety of problems in Combinatorial Optimization. Total domination in graphs was introduced by Cockayne et al. in [2] and is now well studied in graph theory. A survey on this topic can be found in the so-called domination books by Haynes et al. [5, 6].

The study of domination and its variants is motivated by a wide range of applications in real-world network problems, including facility location, social network analysis, and resource allocation. In these contexts, a dominating set represents a collection of nodes that can monitor, serve, or influence the entire network. Total domination, in particular, is crucial for systems requiring redundancy or continuous connectivity, as it ensures that every node—including those in the dominating set—is adjacent to at least one ”active” or ”service” node.

While finding the minimum total dominating set is NP-hard for general graphs, the structural simplicity of caterpillar graphs enables efficient algorithmic solutions and precise combinatorial bounds. Caterpillars often serve as underlying models for linear communication backbones with peripheral nodes, such as a bus topology in local area networks or certain molecular structures in chemistry. Consequently, providing closed-form results or specialized algorithms for total domination in caterpillars not only advances theoretical graph theory but also provides tools for optimizing tree-like hierarchical architectures.

A total dominating set of a graph $G$ (with no isolated vertices) is a set $D$ of vertices of $G$ such that every vertex is adjacent to a vertex in $D$. The total domination problem consists of determining the minimum cardinality of a total dominating set of $G$, denoted by $\gamma_t(G)$.

Given a positive integer number $k$, a natural variation of this concept is the total $\{k\}$-dominating function, generalizing the total dominating set when $k=1$. More precisely, given $G$ and $k$, a function $f: V \longrightarrow\{0,1,\ldots,k\}$ is called total $\{k\}$-dominating function of $G$ if for each $v \in V$, $f(N(v)) = \sum_{u \in N(v)} f(u) \ge k$. The value $f(u)$ is the weight of $f$ on $u$ and for $S \subseteq V$, $f(S) = \sum_{v \in S} f(v)$. The weight of a total $\{k\}$-dominating function $f$ is $f(V)$. The total $\{k\}$-domination number of $G$, $\gamma_t^{\{k\}}(G)$, is the minimum weight of any total $\{k\}$-dominating function of $G$, see [8]. Observe that there is a one-to-one correspondence between the vertices of $G$ at value one in a total $\{1\}$-dominating function and the vertices in a total dominating set. Then, $\gamma_t^{\{1\}}(G) = \gamma_t(G)$.

Given $G$ and a positive integer number $k$, the total $\{k\}$-domination problem (T$\{k\}$DP) consists on finding $\gamma_t^{\{k\}}(G)$. This parameter has been studied by Aram and Sheikholeslam [1], where they provide some tight bounds for this number and determine it exactly for complete multipartite graphs. Also, Haisheng et al. in [4] study the total $\{k\}$-domination number for other basic graph families such as cycles, paths, wheels, and pans. He and Liang in [7] investigate the algorithmic complexity of computing and approximating this number. Regarding the computational complexity of the problem, it was shown in [7] that determining $\gamma_t^{\{k\}}(G)$ is NP-hard for general graphs, even when restricted to certain subclasses such as chordal graphs or bipartite graphs. This complexity remains a significant hurdle for practical applications in large-scale networks, where finding optimal $\{k\}$-dominating configurations is essential for multi-node redundancy and robust coverage.

Given the problem’s intractability in the general case, researchers have focused on identifying graph families for which the T$\{k\}$DP can be solved in polynomial time. Trees, and specifically caterpillar graphs, represent an important frontier in this regard. While caterpillars possess a relatively simple structure—consisting of a central spine with pendant leaves—their asymmetric nature and the flexibility of the $\{k\}$-dominating function weights $\{0,1,\ldots,k\}$ introduce non-trivial combinatorial challenges.

The study of caterpillars in this context is not merely a theoretical exercise; it provides a foundational step for developing dynamic programming approaches and understanding how the ”backbone” structure of a network influences the distribution of dominating weights. In this paper, we take advantage of the structural properties of caterpillars to determine $\gamma_t^{\{k\}}(G)$, thereby extending the existing knowledge on $\{k\}$-domination in trees. In [3] we establish a general bound for the total $\{k\}$-dominating number and a necessary condition for it to be tight in any graph $G$.

It is an interesting problem to determine families of graphs that satisfy this last equality. In this line, the main results in this paper focus on the family of caterpillar graphs.

The remainder of this paper is organized as follows. In § 1, we introduce the fundamental concepts of total $\{k\}$-domination and establish a general upper bound for $\gamma_t^{\{k\}}(G)$. § 2.1 focuses on the structural properties of $D$-caterpillars, demonstrating that for this family, the total $\{k\}$-domination problem can be reduced to the classical total domination problem ($k = 1$). Section ?? constitutes the central methodological framework, introducing the $(T,R)$-representation to encode the graph’s structure and developing the necessary reduction tools. In § 4, we synthesize these findings to present the exact closed-form expression for the total $\{k\}$-domination number applicable to any general caterpillar graph. Finally, § 5 concludes the paper and outlines directions for future research.

A preliminary version of some of the results in this contribution are presented (without proofs) in the conference paper [3].

Previous results on total $k$-domination in caterpillars

Throughout this work, $[n]=\{1,\ldots,n\}$ for any positive integer number $n$.

Given a caterpillar $G=(V,E)$ with $s$ support vertices, we denote $p_i$ a support vertex for every $i\in[s]$. We refer to consecutive support vertices when they are indexed by consecutive numbers, i.e., $p_i$ and $p_{i+1}$ for some $i\in[s-1]$.

In our analysis, we consider general caterpillar graphs and caterpillars in which two consecutive support vertices do not share neighbours. When this is not the case, the two consecutive support vertices can share at most two vertices.

In the following result, we show that it suffices to consider support vertices with disjoint closed neighbourhoods, since the total $k$-domination number of a general caterpillar can be reduced to them.

Proof. In Figure 2 we have represented the construction of $G'$ from the caterpillar $G$. We can first observe that the new caterpillar $\operatorname{Ext}(G)$ has two new disjoint neighbourhoods, i.e., $N(p_i^2)$ and $N(p_i^3)$. Then,

Let $D$ be an optimal total $\{k\}$-dominating set in $G$. We divide the proof into two cases, depending on the number of vertices in the intersection of the closed neighborhoods of $p_i$ and $p_{i+1}$.

• Case 1: $|N_G[p_i] \cap N_G[p_{i+1}]| = 1$

  Let $v \in N_G[p_i] \cap N_G[p_{i+1}]$.

  If $v \in D$, consider $D' = D \cup\{p_i^1,p_i^2\}$. Clearly, $D'$ is also a total $\{k\}$-dominating set achieving the lower bound in 2. Then, it is an optimal total $\{k\}$-dominating set of $\operatorname{Ext}(G)$.

  If $v \notin D$, consider $D' = D \cup\{p_i^3,p_i^4\}$. Again, $D'$ is a total $\{k\}$-dominating set achieving the lower bound in 2 and then an optimal total $\{k\}$-dominating set of $\operatorname{Ext}(G)$. See Figure 2 a).

• Case 2: $|N[p_i] \cap N[p_{i+1}]| = 2$ In this case, $N[p_i] \cap N[p_{i+1}] = \{p_i,p_{i+1}\}$ and $\{p_i,p_{i+1}\} \subseteq D$. If we consider $D' = D \cup\{p_i^2,p_i^3\}$ then $D'$ is an optimal total $\{k\}$-dominating set of $\operatorname{Ext}(G)$. See Figure 2 b).

Proof.

Remark 2.2. The previous lemma can be applied iteratively to obtain a caterpillar in which every pair of consecutive support vertices has disjoint closed neighbourhoods.

This remark allows us to work with caterpillar graphs in which the closed neighbourhoods of two consecutive support vertices are disjoint. Let $G$ be such a caterpillar, following the order of the vertices in the central path, for each support vertex $p_i$ with $i \in\{2,\ldots,s-1\}$, let $p_i^-$ and $p_i^+$ be the neighbours of $p_i$ in $P$. Any time we use the precedence between the indices of the vertices, we consider the order of them according to the vertices in the central path starting from the vertex $p_1$ to $p_s$ (see Figure 3).

Under the previous notation on caterpillars, we first establish that in a caterpillar with disjoint closed support vertices neighbourhoods, there is always an optimal total $\{k\}$-dominating function having value 0 at every leaf and $k$ at every support vertex. More precisely,

Remark 2.4. By Lemma 2.3, the weight of a total $\{k\}$-dominating function in a caterpillar is independent of the number of leaves adjacent to a support vertex. Therefore, we can assume, w.l.o.g., that every support vertex $p_i$ has only one leaf adjacent to it, and denote it as $h_i$ for each $i\in[s]$.

Definition 2.5. Let $G$ be a caterpillar such that every support vertex has one leaf adjacent to it. Moreover, if, for any two consecutive support vertices of $G$, their closed neighborhoods are disjoint, then $G$ is called a D-caterpillar. See Figure 4.

From now on, given a D-caterpillar, we denote by $p_i$ its $i$-th support vertex and by $h_i$ the unique leaf adjacent to it.

On total $k$-domination in D-caterpillars

Let us introduce some useful notation for every D-caterpillar $G$.

According to the previous definition, $G$ can be decomposed into $s-1$ subgraphs of the form $G_i$, where the vertices of $G_i$ and $G_{i+1}$ clearly intersect in $\{p_{i+1},h_{i+1}\}$ for every $i\in[s-2]$. To emphasize this decomposition, we write $G=\bigoplus_{i=1}^{s-1}G_i$. Since $G$ is a D-caterpillar, $n_i\ge6$ for each $i\in[s-1]$. We represent a graph $G_i$ in Figure 5 and $G_i\oplus G_{i+1}$, the paths induced by $P_i$ and $P_{i+1}$ and the leaves $h_i$ and $h_{i+1}$ in Figure 6.

When the D-caterpillar has only two support vertices, the graph itself is a path with at least 6 vertices. Based on the results in [4], Lemma 2.5 in [3] establishes the existence of an optimal total $\{k\}$-dominating function $\{0,k\}$-valued and also a closed formula for the total $\{k\}$-dominating number of paths. We rewrite this result here for completeness.

We extend this result to the case of more than two support vertices in the given D-caterpillar.

The following theorem was originally presented in [3]. However, we include a revised proof of it here, since it provides some intuition on how to define an optimal total $\{k\}$-dominating function, central to our subsequent results.

Proof. We proceed by induction on the number of support vertices $s$ in the D-caterpillar $G$. For the base case $s=2$, the result follows directly from the fact that the caterpillar is a path.

Assume that the statement holds for any D-caterpillar with at most $j$ support vertices. Let $G$ be a D-caterpillar with $s=j+1$ support vertices, which can be viewed as the composition $G=G' \oplus G_j$, where $G'$ is a D-caterpillar containing the first $j$ support vertices and $G_j$ is the subgraph induced by $V_j$ associated with the last two support vertices $p_j$ and $p_{j+1}$.

By the inductive hypothesis, there exists an optimal total $\{k\}$-dominating function $g$ for $G'$ such that $g(v) \in\{0,k\}$ for all $v \in V(G')$. Our goal is to extend or modify $g$ to a function $f$ on $V(G)$ that remains $\{0,k\}$-valued and optimal.

Let $a=g(p_j^{-})$ be the weight assigned to the neighbor of $p_j$ in the central path of $G'$. Based on the weight $g$ assigns to the neighborhood of $p_j$, we define $f$ on $V(G') \setminus\{h_j\}$ to coincide with $g$, while setting $f(h_j)=0=f(h_{j+1})$ to maintain the $\{0,k\}$-property on $G$. To determine the values of $f$ on the path $P_j$ (the vertices between $p_j^+$ and $p_{j+1}^-$) and the final support vertex $p_{j+1}^-$, let $|P_j|=4t_j+r_j$ with $r_j\in\{0,1,2,3\}$.

The total weight of $f$ on $V_j\cup\{p_j^-\}$ must satisfy the following lower bound arising from the total $\{k\}$-domination constraints on $p_j$, $p_{j+1}$, and the $2t_j$ disjoint open neighborhoods within $P_j$:

where $w_l$ are the vertices in the path induced by $P_j$.

We define $f$ on the path induced by $P_j=\{w_1,\ldots,w_{4t_j+r_j}\}$ by alternating weights according to the parity and the boundary value $a\in\{0,k\}$: $f(w_{4t+1})=0$, $f(w_{4t+2})=a$, $f(w_{4t+3})=k$, and $f(w_{4t+4})=k-a$, for $t\in\{0,\ldots,t_j-1\}$.

The definition of $f$ for the remaining vertices depends on $r_j$:

• Case $r_j=0$: Setting $f(p_{j+1}^-)=f(h_{j+1})=0$ achieves the lower bound, ensuring optimality.

• Case $r_j=1$: If $a=k$, we set $f(p_{j+1}^-)=k$ and $f(h_{j+1})=0$. If $a=0$, we set $f(p_{j+1}^-)=0$ and $f(h_{j+1})=k$.

• Case $r_j=2$: Setting $f(p_{j+1}^-)=k$ and $f(h_{j+1})=0$ satisfies the constraints and reaches the lower bound.

• Case $r_j=3$: If $a=0$, we set $f(w_{4t_j+3})=f(p_{j+1}^-)=k$. If $a=k$, we set $f(w_{4t_j+2})=f(w_{4t_j+3})=k$.

In all scenarios, the resulting function $f$ is a total $\{k\}$-dominating function of $G$ with $f(v)\in\{0,k\}$ for all $v\in V(G)$. Since the construction matches the general lower bound for total $\{k\}$-domination in these structures, $f$ is optimal. This completes the induction.

Note that the previous result allows us to study total domination instead of total $\{k\}$-domination in D-caterpillars. More precisely,

Proof. Let $G=(V,E)$ be a D-caterpillar and let $S$ be an optimal total dominating set of $G$ of size $L$. Define the function $f$ on $V$ as $f(v)=k$ for all $v\in S$ and $f(v)=0$ for all $v\in V\setminus S$. Then, it is clearly an optimal total $k$-dominating function of $G$ with weight $kL$.

Conversely, by Theorem 2.8 let $f$ be an optimal total $\{k\}$-dominating function of $G$ $\{0,k\}$-valued weight $kL$. Then the set $S=\{v\in V:f(v)=k\}$ is clearly an optimal total $\{k\}$-dominating set of $G$ of size $L$.

The previous theorem implies that the bound given in Proposition 1.1 for the total $\{k\}$-domination number is achieved for the family of all D-caterpillars. Also, this result shows that, to study $\{k\}$-domination in this family, we can restrict our attention to the problem of total domination in graphs.

Total domination in D-caterpillars

In the proof of Theorem 2.8, we observed that the congruence modulo 4 of the number of vertices in the paths induced between consecutive support vertices plays a decisive role in determining the optimal weight distribution. This section formalizes this observation by introducing a compact representation for D-caterpillars.

On the representation of a D-caterpillar

While the previous results establish the reduction of the total $\{k\}$-domination problem to the case $k=1$, a significant challenge remains: providing an exact closed-form expression for $\gamma_t(G)$ for any caterpillar $G$. The difficulty lies in the asymmetric distribution of weights across the central path and the sensitivity of the total weight to the specific lengths of the paths between support vertices.

To address this, we introduce the $(T,R)$-representation, a combinatorial framework that abstracts the nature of a D-caterpillar into two discrete vectors. By considering congruence modulo 4 in the segments of the central path between the open neighbourhood of two consecutive support vertices, we define the integer-valued vectors $T$ and $R$, and provide a one-to-one mapping between the family of D-caterpillars and the specific discrete space. This representation is not merely descriptive; it serves as a fundamental tool to derive the exact total domination number.

We illustrate this definition in an example; see Figure 7.

Based on the components of the remainder vector $R$, we can partition the subgraphs $G_i$ into the index sets:

• $I_0 = \{1,7\}$, $I_1 = \{2,3,11\}$, $I_2 = \{4\}$, and $I_3 = \{5,6,8,9,10\}$.

Furthermore, the vector $R$ contains two maximal sequences of consecutive 3s ($m = 2$):

• $\mathcal{G}_1 = \{G_5,G_6\}$ with length $\ell_1 = 2$.

• $\mathcal{G}_2 = \{G_8,G_9,G_{10}\}$ with length $\ell_2 = 3$.

Given a D-caterpillar $G$ we define a smaller D-caterpillar $G'$ having a $\{0,2,3\}$-valued vector $R(G')$ in its $(T(G'),R(G'))$-representation. This reduction will be useful for determining the total domination number of $G$. See Theorem 3.14.

On the total domination number in D-caterpillar

We begin this section by presenting some properties satisfied by an optimal total dominating function on a D-caterpillar that will be useful for presenting the main result of this section, i.e., the total domination number of a general D-caterpillar. Recall that in a D-caterpillar with support vertices $p_i$ for $i \in[s]$, $p_i^{-}$ is previous neighbour of $p_i$ in the central path of $G$ and $p_i^{+}$ is subsequent neighbour of $p_i$ in the central path of $G$.

According to the particular neighbourhood of support vertices in D-caterpillars, in the following lemma, we show that we can consider two different possible assignments in an optimal total dominating function.

Proof. By Lemma 2.3, there is an optimal total dominating function $f$ such that $f(h_i)=0$ and $f(p_i)=1$ for all $i \in[s]$. Since $N(p_1)=\{p_1^{+}\}$, $N(p_i)=\{p_i^{-},p_i^{+}\}$ for all $i \in\{2,\ldots,s-1\}$ and $N(p_s)=\{p_s^{-}\}$ the optimality of $f$ proves the result.

If the D-caterpillar is decomposed according to Definition 2.6, the previous lemma helps in determining the value of an optimal total dominating function on each graph $G_i$.

ii)

if $f(p_i^-)=f(p_i)=1$.

Proof. Given the D-caterpillar $G$, in its $(T,R)$-representation, the components of $T$ and $R$, $t_i$ and $r_i$, are the non-negative integer numbers such that $|P_i|=4t_i+r_i$ and $r_i\leq3$, for $i\in[s-1]$. Let $i\in[s-1]$ and assume that $P_i=\{w_1,\ldots,w_{b_i}\}$.

According to Lemma 3.7 there exists an optimal total dominating function $\tilde{f}$ satisfying either that $\tilde{f}(p_i)=\tilde{f}(p_i^+)=1$ or $\tilde{f}(p_i^-)=\tilde{f}(p_i)=1$. In addition, it holds that

i) Suppose first that $\tilde{f}(p_i)=\tilde{f}(p_i^+)=1$.

If $r_i\in\{0,1\}$ we define a total dominating function $f$ as

for $t\in\{0,\ldots,t_i-1\}$, achieves the value $f(P_i)=2t_i$, thus proving its optimality due to (7).

Note that $[r_i]=\emptyset$ if $r_i=0$.

In case $r_i=2$,

for $t\in\{0,\ldots,t_i-1\}$, achieves the value $f(P_i)=2t_i$. Again, this proves its optimality due to (7).

Similarly, when $r_i=3$, we define the total dominating function $f$ as

for $t \in\{0,\ldots,t_i-1\}$, achieves the lower bound $2t_i+1$ given by (7), and then proving its optimality.

ii) Assume now that $\tilde{f}(p_i^-)=\tilde{f}(p_i)=1$.

If $r_i=0$, we define the total dominating function $f$ as

for $t\in\{0,\ldots,t_i-1\}$, achieves the value $f(P_i)=2t_i$, thus proving its optimality due to (7).

Similarly, when $r_i=1$, the total dominating function $f$ is defined as

for $t\in\{0,\ldots,t_i-1\}$, and it achieves the value $f(P_i)=2t_i$ thus proving its optimality due to (7).

When $r_i=2$, the function $f$ is defined as

for $t\in\{0,\ldots,t_i-1\}$.

Finally, when $r_i=3$ the function $f$ is defined as

for $t\in\{0,\ldots,t_i-1\}$.

In both cases, $f$ is clearly a total dominating function of $G$. Also note that when $r_i\in\{2,3\}$, the set $P_i\cup\{p_{i+1}^-\}$ can be partitioned into $2t_i+(r_i-1)$ disjoint open neighbourhoods of vertices of $G$. Then, this function achieves optimality using the bound provided by (7).

In the next observation, we explicitly show that there is always an optimal total dominating function that takes into account the two possible situations considered in Lemma 3.7 to define its value in the neighbourhood of the following support vertex. More precisely, after the proof of Lemma 3.8, we can state the following.

According to the previous result we are in a position of determining the total domination number of the caterpillar for which its $(T,R)$-representation coincides with the $(T',R')$-representation given in Definition 3.5. This provides a basic reduction for obtaining the total domination number for general caterpillar graphs.

Recall that, given a D-caterpillar such that $G = \bigoplus_{i=1}^{s-1}G_i$, the value of the total domination number of any $G_i$ can be obtained by the results in [4], for each $i \in[s-1]$ since they are actually paths in the original graph $G$. Recall that we have already know the total domination number of paths and then then we consider $s \geq3$ in the next proposition and the particular situation where $I_0 = I_1 = \varnothing$. We fundament this assumption in the subsequent results.

where

for $i \in[2,s-1]$.

If $I_2=\varnothing$,

Proof. Lemma 3.7 and Lemma 3.8 imply that there exists an optimal total dominating function $f$ such that: $f(p_1)=f(p_1^+)=1$ and

Assume first that $I_2\ne\varnothing$.

By hypothesis, we have to consider only four combinations of $r_{i-1}$ and $r_i$, for $i\in[2,s-1]$, i.e., $r_{i-1}\in\{2,3\}$ and $r_i\in\{2,3\}$.

• Case $r_{i-1}=2$ and $r_i=2$.

From Remark 3.9, $f(p_i^-)=f(p_i)=1$ and then, Lemma 3.8 implies that $f(P_i)=2t_i+1=2t_i+E_i$.

• Case $r_{i-1}=2$ and $r_i=3$.

From Remark 3.9, $f(p_i^-)=f(p_i)=1$ and then Lemma 3.8 implies that $f(P_i)=2t_i+2=2t_i+E_i+2$.

• Case $r_{i-1}=3$ and $r_i=2$.

If $f(p_{i-1}^+)=f(p_{i-1})=1$ then $f(p_i^+)=f(p_i)=1$, and Lemma 3.8 implies that $f(P_i)=2t_i$.

If $f(p_{i-1}^+)=f(p_{i-1})=1$ then $f(p_i^-)=f(p_i)=1$, implying that $f(P_i)=2t_i+1$.

• Case $r_{i-1}=3$ and $r_i=3$.

If $f(p_{i-1}^-)=f(p_{i-1})=1$, Remark 3.9 implies that $f(p_i^-)=f(p_i)=1$. Then, $f(P_{i-1})=2t_{i-1}+1$ and $f(P_i)=2t_i+2$. Analogously, if $f(p_{i-1}^+)=f(p_{i-1})=1$, Remark 3.9 implies that $f(p_i^+)=f(p_i)=1$. Then, $f(P_{i-1})=2t_{i-1}+2$ and $f(P_i)=2t_i+1$. In either case, for every pair of consecutive components of $R$ with value 3, we have 3 more units in the value of the optimal total dominating function $f$.

Let us now consider the value of this optimal total dominating function $f$ in $\ell_0$ according to the value of $r_1$.

• If $r_1=2$, without loss of generality, we analyze the case $r_{i_0-1}=2$ and $r_{i_0}=3=\ldots=r_{i_0+\ell_j-1}=3$ for some $\ell_j$, for $i_0\ge2$. After Lemma 3.8 and Remark 3.9, $f(p_{i_0}^{-})=f(p_{i_0})=1$. Therefore, the previous analysis shows that, for each pair of consecutive $r_{i-1}=r_i=3$ we have $f(P_{i-1})+f(P_i)=2t_{i-1}+2t_i+3$. Obtaining $3\left\lfloor\frac{\ell_j}{2}\right\rfloor$ extra units in the value of optimal total dominating function.

When $\ell_j$ is odd, we also have that $f(p_{i_0+\ell_j-1}^{-})=f(p_{i_0+\ell_j-1})=1$ and then $f(P_{i_0+\ell_j-1})=2t_{i_0+\ell_j-1}+2$.

which can be rewritten as,

Therefore,

• If $r_1=3$ then $r_{\ell_1+1}=2$. Following a similar analysis as in the previous case, we have two different situations according to the parity of $\ell_1$. When $\ell_1$ is even, $f(p_{\ell_1+1}^{+})=f(p_{\ell_1+1})=1$ and then $f(P_{\ell_1+1})=2t_{\ell_1+1}$. If not, $f(p_{\ell_1+1}^{-})=f(p_{\ell_1+1})=1$ and then $f(P_{\ell_1+1})=2t_{\ell_1+1}+1$. Again,

taking into account that for each pair of consecutive $r_{i-1}=r_i=3$ we have $f(P_{i-1})+f(P_i)=2t_{i-1}+2t_i+3$,

which can be rewritten as,

Also, the value of $f(P_{\ell_1+1})$ can be expressed as $f(P_{\ell_1+1})=2t_{\ell_1+1}+\ell_1-2\left\lfloor\frac{\ell_1}{2}\right\rfloor$. Then

Proving that the result in 8 follows.

Finally, if $I_2=\emptyset$ the previous analysis is simplified since we have $m=1$ and $\ell_1=s-1$. Then,

thus proving 9.

Although the hypothesis in Proposition 3.10 look quite restrictive, combining it with the reduction proposed in Definition 3.5, this result is crucial for finding the value of the total domination number of a general $D$-caterpillar.

In the previous result, we did not consider D-caterpillars with $I_0\ne\emptyset$. In this case, we split the graph $G$ into D-caterpillar subgraphs with the property of having all the components of their $R$-vectors in their $(T,R)$-representation either equal to zero or all different from zero. More precisely,

Note that when $I_0=\emptyset$, the $I_0$-split decomposition of $G$ results in the original graph $G$.

According to the definition of the $I_0$-split decomposition of a $D$-caterpillar, we need to explicitly determine the value of the total domination number on two different type of $D$-caterpillars.

Proof. If $I_0 = \emptyset$, after Proposition 3.10, we need to consider only the case when $r_i = 1$, i.e., $i \in I_1$. By Lemma 3.7, there exists an optimal total dominating function $f$ satisfying $f(p_i^+) = f(p_i) = 1$ or $f(p_i^-) = f(p_i) = 1$. In any of these two possible situations, since $r_i = 1$, Remark 3.9 shows that $f(p_{i+1}^+) = f(p_{i+1}) = 1$ or $f(p_{i+1}^-) = f(p_{i+1}) = 1$, respectively. Moreover, since $f(P_i) = 2t_i$ and $f(N[p_i]) = 2$ we have that

If $I_0 = [s-1]$ the vector $R$ is the zero vector. We can assume that there exists an optimal total dominating function $f$ satisfying $f(p_1^+) = f(p_1) = 1$. Since $r_1 = 0$, Remark 3.9 shows that $f(p_i^+) = f(p_i) = 1$ for every $i \in[s-1]$ and then $f(P_i) = 2t_i$. Finally, the value of $f$ in the closed neighbourhood of the support vertices proves the result.

We are now in a position to present a closed formula for total domination in a $D$-caterpillar, based on the result in Proposition 3.10, the reductions proposed in Definition 3.5, Definition 3.11 and Lemma 3.13.

Proof. The result clearly follows when $I_0 = \emptyset$, due to Lemma 3.13 and Proposition 3.10.

Assume now that $I_0 \ne\emptyset$ and let $\{(T^j,R^j) : j \in J\}$ be its $I_0$-split decomposition.

Using the same reasoning as in the previous proofs, and taking into account the definition of each $G^j$, there exists an optimal total dominating function $f$ in $G$ such that $f(p_j^+) = f(p_j) = 1$ for each $p_j$ with $j \in J$. Then, in two consecutive graphs $G^{j_1}$ and $G^{j_2}$ (following the order of the vertices in the central path of $G$) we can sum-up the value of $f$ but taking into account its value on the closed neighbourhood of the support vertex they share in $G$. More precisely, if $G^{j_1}$ and $G^{j_2}$ are consecutive subgraphs in $G$ they share (in $G$) the last support vertex of $G^{j_1}$, $p_{j_1+1}$, and its adjacent leaf $h_{j_1+1}$. Then, to obtain the value of the total domination number of $G$, we subtract two units (for the closed neighbourhood of the common support vertex) for each of pair of consecutive graphs in the $I_0$-split decomposition of $G$.

Then 11 implies that

and

Finally, since $J=\{1,2,7,8\}$,

Total $k$-domination in caterpillars

This last section is devoted to present the main result of this contribution, that is, a closed formula for the total $\{k\}$-domination in a general caterpillar graph.

In Lemma 2.1 it is proved that we can recursively apply an extension of the original graph to obtain a caterpillar where all the support vertices have disjoint closed neighbourhoods, and, according to 1, the $\{k\}$-domination number of the original graph can be obtained from the one of the extension. Lemma 2.3 shows that without loss of generality we can assume that each support vertex has exactly one leaf adjacent to it.

Therefore, we can restrict to D-caterpillar in the rest of the analysis. Finally, Theorem 2.8 allow us to study the problem of total domination in D-caterpillar, and gives the $\{k\}$-domination number of the original graph in terms of the total domination number of it.

Conclusions and Future Work

In this paper, we have investigated the total $\{k\}$-domination number, $\gamma_t^{\{k\}}(G)$, focusing on the class of caterpillar graphs. We established a general upper bound for this parameter and identified sufficient conditions for a graph to attain equality. Furthermore, we proved that this bound is tight for the family of caterpillars by showing that the total $\{k\}$-domination problem ($\mathrm{T}\{k\}\mathrm{DP}$) reduces to the classical total domination problem ($k=1$), yielding the relation $\gamma_t^{\{k\}}(G)=k\gamma_t(G)$. To achieve this, we introduced a novel $(T,R)$-representation for caterpillars based on the number of support vertices and the lengths of the paths induced between them along the central path. By exploiting this structural representation and analyzing the underlying congruence modulo 4, we obtained a closed-form expression for the exact total $\{k\}$-domination number of any caterpillar graph for all values of $k$.

Several interesting lines of research remain open. A natural extension of this work is to determine whether the reduction $\gamma_t^{\{k\}}(G)=k\gamma_t(G)$ holds for all trees, which would generalize our findings beyond the caterpillar family. Additionally, future research could focus on identifying other structural properties that enable wider classes of graphs to achieve the general upper bound provided in Proposition 1.1, thereby expanding the contexts in which the $\mathrm{T}\{k\}\mathrm{DP}$ can be simplified to the classical case.