Complexity aspects of variants of independent Roman domination in graphs

DOI10.1007/S41980-020-00468-5MaRDI QIDQ2666348zbMATH OpenOpenAlexFDO

Authors Chakradhar Padamutham, Venkata Subba Reddy Palagiri

Publication date 22 November 2021

Published in Bulletin of the Iranian Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s41980-020-00468-5

zbMATH Keywords

APX-hardindependent double Roman dominationindependent Roman \(\{2\}\)-dominationindependent Roman dominationNP-complete

Mathematics Subject Classification ID

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

Recommendations

• Independent Roman \(\{3\}\)-domination
• Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
• Independent double Roman domination in graphs
• Independent Roman \(\{2 \}\)-domination in graphs
• Algorithmic aspects of Roman domination in graphs

Cites work

• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• Algorithms and Computation
• Counting independent sets in tree convex bipartite graphs
• Double Roman domination
• Double Roman domination number
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Independent double Roman domination in graphs
• Independent Roman \(\{2 \}\)-domination in graphs
• Introduction to algorithms
• Node-and edge-deletion NP-complete problems
• On the double Roman domination in graphs
• On the Roman domination number of a graph
• Properties of independent Roman domination in graphs
• Roman \(\{2 \}\)-domination
• Roman domination in graphs.
• Roman domination perfect graphs
• Strong equality between the Roman domination and independent Roman domination numbers in trees
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Threshold graphs and related topics
• Trees with equal Roman \{2\}-domination number and independent Roman \{2\}-domination number

Cited in

(9)

• On the complexity of some hop domination parameters
• Independent Roman \(\{3\}\)-domination
• Further results on the independent Roman domination number of graphs
• Efficient algorithms for independent Roman domination on some classes of graphs
• Roman domination and independent Roman domination on graphs with maximum degree three
• Complexity aspects of restrained Roman domination in graphs
• Domination in diameter-two graphs and the 2-club cluster vertex deletion parameter
• Exploring algorithmic solutions for the independent Roman domination problem in graphs
• Algorithmic results on independent Roman \(\{2\}\)-domination

This page was built for publication: Complexity aspects of variants of independent Roman domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2666348)