On maximal Roman domination in graphs: complexity and algorithms

DOI10.1051/RO/2024038MaRDI QIDQ6593946zbMATH OpenFDO

Authors Zehui Shao, Yonghao Song, Qiyun Liu, Zhixing Duan, Huiqin Jiang

Publication date 27 August 2024

Published in RAIRO. Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/RO/2024038

zbMATH Keywords

block graphsmaximal Roman dominationNP-completenessthreshold graphstrees

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On maximal Roman domination in graphs
• scientific article; zbMATH DE number 6769213
• Maximal double Roman domination in graphs
• Algorithmic aspects of Roman domination in graphs
• Connected graphs with maximal Roman domination number one less than their order.

Cites work

• A Characterization of Block-Graphs
• Algorithmic aspects of Roman domination in graphs
• Connected graphs with maximal Roman domination number one less than their order.
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Global Roman domination in graphs
• Graph theory with applications
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6769213 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• Maximal 2-rainbow domination number of a graph
• Maximal double Roman domination in graphs
• On computing a minimum secure dominating set in block graphs
• On maximal Roman domination in graphs
• Outer independent Roman dominating functions in graphs
• Perfect Roman domination in graphs
• Roman domination in graphs.
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The probabilistic method
• Threshold graphs and related topics
• Total Roman domination subdivision number in graphs
• Varieties of Roman Domination
• Varieties of Roman domination. II

This page was built for publication: On maximal Roman domination in graphs: complexity and algorithms

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