Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.07020 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Let $\{0,1,\dots, t\}$ be abbreviated by $[t].$ A double Roman dominating function (DRDF) on a graph $Γ=(V,E)$ is a map $l:V\rightarrow [3]$ satisfying \textrm{(i)} if $l(r)=0$ then there must be at least two neighbors labeled 2 under $l$ or a neighbor $r'$ with $l(r')=3$; and \textrm{(ii)} if $l(r)=1$ then $r$ must be adjacent to a vertex $r'$ such that $l(r')\geq2$. A DRDF is an outer-independent total double Roman dominating function (OITDRDF) on $Γ$ if the set of vertices labeled $0$ induces an edgeless subgraph and the subgraph induced by the vertices with a non-zero label has no isolated vertices. The weight of an OITDRDF is the sum of its map values over all vertices, and the outer independent total Roman dominating number $γ_{tdR}^{oi}(Γ)$ is the minimum weight of an OITDRDF on $Γ$. First, we prove that the problem of determining $γ_{tdR}^{oi}(Γ)$ is NP-complete for bipartite and chordal graphs, after that, we prove that it is solvable in linear time when we are restricting to bounded clique-width graphs. Moreover, we present some tight bounds on $γ_{tdR}^{oi}(Γ)$ as well as the exact values for several graph families.