On algorithmic complexity of double Roman domination
A double Roman dominating function on a graph \(G=(V,E)\) is a function \(f:V\rightarrow \{0,1,2,3\}\) such that every vertex \(v \in V\) with \(f(v)=0\) is either adjacent to a vertex \(u\) with \(f(u)=3\) or two distinct vertices \(x\) and \(y\) with \(f(x)=f(y)=2\), and every vertex \(v \in V\) with \(f(v)=1\) is adjacent to a vertex \(u\) with \(f(u)\geq 2\). The weight of \(f\) is the sum \(f(V)=\sum_{v \in V}f(v)\). The minimum weight of a double Roman domination function of \(G\), denoted by \(\gamma_{\mathrm{dR}}(G)\) is called the double Roman domination number of graph \(G\). A graph \(G\) is a double Roman graph if \(\gamma_{\mathrm{dR}}(G)=3\gamma(G)\), where \(\gamma(G)\) is the domination number of \(G\). In the paper under review, the authors prove (a) the decision problem associated with double Roman domination is NP-complete even when restricted to planar graphs (b) the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. The authors also propose a linear algorithm to compute the domination number and the double Roman domination number of a given unicyclic graph and conclude with a linear algorithm to decide whether a given unicyclic graph is double Roman graph.
- Defendens Imperium Romanum: A Classical Problem in Military Strategy
- Double Roman domination
- Double Roman domination in trees
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 7362655 (Why is no real title available?)
- On the double Roman domination in graphs
- On the double Roman domination of graphs
- Planar Formulae and Their Uses
- Roman domination in graphs
- Roman domination in graphs.
- Some progress on the double Roman domination in graphs
- Varieties of Roman domination. II
- Some progress on the double Roman domination in graphs
- Algorithm and hardness results in double Roman domination of graphs
- Maximal double Roman domination in graphs
- Algorithmic results on double Roman domination in graphs
- Algorithmic and complexity aspects of problems related to total Roman domination for graphs
- On the double Roman domination in graphs
- Varieties of Roman Domination
- Algorithmic aspects of Roman graphs
- Bounds on the outer-independent double Italian domination number
- On the complexity of some hop domination parameters
- Double Roman domination in graphs: algorithmic complexity
- Solving the minimum-cost double Roman domination problem
- The k-th Roman domination problem is polynomial on interval graphs
This page was built for publication: On algorithmic complexity of double Roman domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197468)
