Perfect Roman domination in graphs

DOI10.1016/J.TCS.2019.08.017MaRDI QIDQ2333784zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.08.017

zbMATH Keywords

NP-completenessdominationRoman dominationpolynomial time algorithmperfect Roman domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Complexity issues of perfect Roman domination in graphs
• On perfect Roman domination number in trees: complexity and bounds
• Perfect Roman domination in trees
• On the computational complexity aspects of perfect Roman domination
• Perfect Roman domination in regular graphs

Cites work

• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A linear algorithm for the domination number of a series-parallel graph
• A linear time recognition algorithm for proper interval graphs
• Complement reducible graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Double Roman domination
• Perfect Roman domination in regular graphs
• Perfect Roman domination in trees
• Planar 3DM is NP-complete
• Roman \(\{2 \}\)-domination
• Roman domination in graphs.
• Signed Roman domination in graphs

Cited in

(23)

• Perfect Roman domination in trees
• Complexity issues of perfect Roman domination in graphs
• Perfect Italian domination in cographs
• Roman domination on strongly chordal graphs
• Perfect double Roman domination in graphs
• Perfect Italian domination in graphs: complexity and algorithms
• Efficient algorithms for Roman domination on some classes of graphs
• Double vertex-edge domination in graphs: complexity and algorithms
• Roman \(\{3\}\)-domination in graphs: complexity and algorithms
• Perfect Roman domination in middle graphs
• On perfect Roman domination number in trees: complexity and bounds
• On the computational complexity aspects of perfect Roman domination
• Note on the perfect Roman domination number of graphs
• Perfect Roman domination in regular graphs
• Unique response Roman domination: complexity and algorithms
• Domination problems on \(P_{5}\)-free graphs
• Total Roman domination for proper interval graphs
• On maximal Roman domination in graphs: complexity and algorithms
• The restrained double Roman domination in graphs
• On the perfect differential of a graph
• A linear-time algorithm for weighted paired-domination on block graphs
• Roman domination perfect graphs
• Perfect Domination, Roman Domination and Perfect Roman Domination in Lexicographic Product Graphs

This page was built for publication: Perfect Roman domination in graphs

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