The triple Roman domination stability in graphs
Acta mathematica Universitatis Comenianae, Tome 94 (2025) no. 3, pp. 145-160
Citer cet article
Voir la notice de l'article provenant de la source Comenius University
A triple Roman dominating function (TRDF) on a graph $G$ is a function $f :V(G)\to \{0, 1, 2, 3, 4\}$ satisfying the condition that for every vertex $v\in V(G)$ with $f(v)< 3$, $f(N_G[v])\geq |AN(v)|+3$, where $AN(v)$ is the set of vertices $w\in N_G(v)$ such that $h(w)\geq 1$. The weight of a TRDF $f$ is $\sum_{v\in V(G)}f(v).$ The triple Roman domination number $\gamma_{[3R]}(G)$ is the minimum weight of an TRDF on $G$. The $gamma_{[3R]}$-stability ($\gamma^-_{[3R]}$-stability, $\gamma^+_{[3R]}$-stability) of $G$, denoted by ${\rm st}_{\gamma_{[3R]}}(G) $ (${\rm st}^-_{\gamma_{[3R]}}(G)$, ${\rm st}^+_{\gamma_{[3R]}}(G)$), is defined as the minimum size of a set of vertices whose removal changes (decreases, increases) the triple Roman domination number. In this paper, we determine the exact values of the $\gamma_{[3R]}$-stability of some special classes of graphs, and present some bounds on ${\rm st}_{\gamma_{[3R]}}(G)$. Furthermore, for a tree $T$ with maximum degree $\Delta$, we show that ${\rm st}_{\gamma_{[3R]}}(T)=1 $ and ${\rm st}^-_{\gamma_{[3R]}}(T)\le \Delta $, and we characterize the trees that achieve the upper bound.