Complexity of Roman {2}-domination and the double Roman domination in graphs

DOI10.1016/j.akcej.2020.01.005zbMath1468.05217OpenAlexW3047937642MaRDI QIDQ4956233

Chakradhar Padamutham, Venkata Subba Reddy Palagiri

Publication date: 1 September 2021

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.akcej.2020.01.005

zbMATH Keywords

approximation algorithmNP-completetree convex bipartite graphsdouble Roman dominationRoman \(\{ 2 \} \)-domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ On the watching number of graphs using discharging procedure ⋮ On the computational complexity of Roman\(\{2\}\)-domination in grid graphs ⋮ Unique response Roman domination: complexity and algorithms ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ Independent roman $\{3\}$-domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Roman \(\{2 \}\)-domination
• Double Roman domination
• Counting independent sets in tree convex bipartite graphs
• Roman domination in graphs.
• Double Roman domination number
• On the double Roman domination in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Node-and edge-deletion NP-complete problems

This page was built for publication: Complexity of Roman {2}-domination and the double Roman domination in graphs