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

dominationNP-completenessperfect Roman dominationpolynomial time algorithmRoman domination

Mathematics Subject Classification ID

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

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

• A linear algorithm for the domination number of a series-parallel graph
• A Linear Recognition Algorithm for Cographs
• A linear time recognition algorithm for proper interval graphs
• Complement reducible graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Double Roman domination
• 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?)
• 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

(26)

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

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)