On weak double Roman domination in graphs
The dominating functions under investigation here have their historical origin in Roman defense strategies, (cf.\ [\textit{R. A. Beeler} et al., Discrete Appl. Math. 211, 23--29 (2016; Zbl 1348.05146)]). For a graph \(G=(V,E)\), a double Roman dominating function \(f_0:V\to\{0,1,2,3\}\) is constrained as follows for each \(v\in V\): if \(f_0(v)=0\), then \(f_0\) must assign either (i) to at least two neighbors of \(v\) the value 2, or (ii) to at least one neighbor the value 3; and, if \(f_0(v)=1\), then \(f_0\) must assign to at least one neighbor of \(v\) a value not less than 2. The authors apply a less restrictive variant -- the weak double Roman dominating function (WDRD-function) \(f:V\to\{0,1,2,3\}\) -- which they introduced in [\textit{S. Soltani} et al., Bull. Malays. Math. Sci. Soc. (2) 47, No. 6, Paper No. 184, 18 p. (2024; Zbl 1557.05123)]; the weight of \(f\) is \(\sum_{v\in V}f(v)\), and the weak double Roman domination number \(\gamma_{\mathrm{wdR}}(G)\) equals the minimum weight of any WDRD-function on \(G\). The weak function is constrained as follows: when \(f(v)\le1\) for \(v\in V\), there must exist a neighbor \(u\) of \(v\) with \(f(u)\ge2\), such that the modified function \(g:V\to\{0,1,2,3\}\) defined by \(g(v)=f(v)+1\), \(g(u)=f(u)-1\) and \(g(x)=f(x)\) for all \(x\in V\) other than \(u\) and \(v\), has no doubly unprotected vertex \(w\) -- i.e. such that \(\sum_{x\in N[w]}g(x)>1\) for all \(w\in V\) (where \(N[w]\) denotes the closed neighborhood of \(w\), consisting of \(w\) and all vertices adjacent to \(w\)). A bipartite graph \(G=(X,Y,E)\) is tree convex if a tree \(T=(X,F)\) can be defined such that the neighbors of any \(y\in Y\) induce a subtree in \(T\); \(G\) is star convex if \(T\) is a star.\N\NHaving proved, in Theorem 5 of [Soltani et al., loc. cit.], that the weak double Roman domination problem (WDRD) is NP-complete for bipartite graphs, the authors now ask, in the instance of a nonempty star convex bipartite graph \(G\) and a positive integer \(r\), whether \(G\) has a WDRD-function of weight at most \(r\); they prove Theorem 1: The problem WDRD is NP-complete for star convex bipartite graphs. Theorem 4 addresses part of Problem 4 in \S6 of the earlier paper, to characterize nontrivial trees \(T_1\) where the minimum cardinality of any dominating set, \(\gamma(T_1)\), is equal to \(\frac12\gamma_{\mathrm{wdR}}(T_1)\). For perfect binary trees, the authors determine the exact value of \(\gamma_{\mathrm{wdR}}\) in Theorem 8: For any perfect binary tree \(T_2\) in which each internal vertex has two children, and all leaves have depth \(k\ge1\), \(\gamma_{\mathrm{wdR}}(T_2)=3\left(2^2+2^5+\dots+2^{k-1}\right)+2\) if \(k\equiv0\pmod 3\); \(\gamma_{\mathrm{wdR}}(T_2)=3\left(2^0+2^3+\dots+2^{k-1}\right)\) if \(k\equiv1\pmod3\); \(\gamma_{\mathrm{wdR}}(T_2)=3\left(2^1+2^4+2^7+\dots+2^{k-1}\right)\) if \(k\equiv2\pmod3\). Moreover, \(T_2\) has a unique \(\gamma_{\mathrm{wdR}}(T_2)\)-function when \(k\equiv1,2\pmod3\), and \(T_2\) has exactly three \(\gamma_{\mathrm{wdR}}(T_2)\)-functions when \(k\equiv0\pmod 3\).
- Critical concept for double Roman domination in graphs
- Disprove of a conjecture on the double Roman domination number
- Double Roman domination
- Double Roman domination in graphs with minimum degree at least two and no \(C_5\)-cycle
- Double Roman domination in graphs: algorithmic complexity
- Quasi total double Roman domination in trees
- Restrained condition on double Roman dominating functions
- Weak double Roman domination
This page was built for publication: On weak double Roman domination in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906740)
