Total Roman bondage number of a graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914315812995072 |
|---|---|
| author | Ghasr, Fahimeh Khosh-Ahang Nazari-Moghaddam, Sakineh |
| author_facet | Ghasr, Fahimeh Khosh-Ahang Nazari-Moghaddam, Sakineh |
| contents | A total Roman dominating function (TRDF) on a graph $G$ with no isolated vertices is a function $f:V(G)\to\{0,1,2\}$ such that every vertex $v$ with $f(v)=0$ has a neighbor assigned $2$, and the subgraph induced by $\{v:f(v)>0\}$ has no isolated vertices. The total Roman domination number $γ_{tR}(G)$ is the minimum weight of a TRDF on $G$. The total Roman bondage number $b_{tR}(G)$ is the minimum cardinality of an edge set $E'\subseteq E(G)$ such that $G-E'$ has no isolated vertices and $γ_{tR}(G-E')>γ_{tR}(G)$; if no such $E'$ exists, $b_{tR}(G)=\infty$.
We prove that deciding whether $b_{tR}(G)\leq k$ is NP-complete for arbitrary graphs. We establish sharp bounds, including $γ_{tR}(G)+1\leq γ_{tR}(G-B)\leq γ_{tR}(G)+2$ for any $b_{tR}(G)$-set $B$ (both sharp), and $b_{tR}(G)\geq \max\{δ(G),b(G)\}$ when $γ_{tR}(G)=3β(G)$. We characterize graphs with $b_{tR}(G)=\infty$ and provide a necessary and sufficient condition for $b_{tR}(G)=1$. Exact values are determined for complete graphs, complete bipartite graphs, brooms, double brooms, wheels and wounded spiders.
Further upper bounds are given in terms of order, diameter, girth, and structural features. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08758 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Total Roman bondage number of a graph Ghasr, Fahimeh Khosh-Ahang Nazari-Moghaddam, Sakineh Combinatorics 05C69 A total Roman dominating function (TRDF) on a graph $G$ with no isolated vertices is a function $f:V(G)\to\{0,1,2\}$ such that every vertex $v$ with $f(v)=0$ has a neighbor assigned $2$, and the subgraph induced by $\{v:f(v)>0\}$ has no isolated vertices. The total Roman domination number $γ_{tR}(G)$ is the minimum weight of a TRDF on $G$. The total Roman bondage number $b_{tR}(G)$ is the minimum cardinality of an edge set $E'\subseteq E(G)$ such that $G-E'$ has no isolated vertices and $γ_{tR}(G-E')>γ_{tR}(G)$; if no such $E'$ exists, $b_{tR}(G)=\infty$. We prove that deciding whether $b_{tR}(G)\leq k$ is NP-complete for arbitrary graphs. We establish sharp bounds, including $γ_{tR}(G)+1\leq γ_{tR}(G-B)\leq γ_{tR}(G)+2$ for any $b_{tR}(G)$-set $B$ (both sharp), and $b_{tR}(G)\geq \max\{δ(G),b(G)\}$ when $γ_{tR}(G)=3β(G)$. We characterize graphs with $b_{tR}(G)=\infty$ and provide a necessary and sufficient condition for $b_{tR}(G)=1$. Exact values are determined for complete graphs, complete bipartite graphs, brooms, double brooms, wheels and wounded spiders. Further upper bounds are given in terms of order, diameter, girth, and structural features. |
| title | Total Roman bondage number of a graph |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2602.08758 |