Strong equality of Roman and weak Roman domination in trees

DOI10.1016/J.DAM.2016.03.004MaRDI QIDQ284830zbMATH OpenOpenAlexFDO

Authors José D. Alvarado, Simone Dantas, Dieter Rautenbach

Publication date 18 May 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04902

zbMATH Keywords

Roman dominationweak Roman dominationstrong equality

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We provide a constructive characterization of the trees for which the Roman domination number strongly equals the weak Roman domination number, that is, for which every weak Roman dominating function of minimum weight is a Roman dominating function. Our characterization is based on five simple extension operations, and reveals several structural properties of these trees.

Recommendations

• Constructive characterizations concerning weak Roman domination in trees
• Strong equality between the Roman domination and independent Roman domination numbers in trees
• Trees \(T\) with weak Roman domination number being equal to domination number
• Strong equality of Roman and perfect Roman domination in trees
• Trees with equal strong Roman domination number and Roman domination number

Cites work

• scientific article; zbMATH DE number 1507962 (Why is no real title available?)
• A characterization of Roman trees
• Bounds on weak Roman and 2-rainbow domination numbers
• Characterizations of trees with equal domination parameters
• Construction of trees and graphs with equal domination parameters
• Defending the Roman Empire---a new strategy
• Paired-domination in graphs
• Strong equality between the Roman domination and independent Roman domination numbers in trees
• Strong equality of domination parameters in trees
• Trees with strong equality between the roman domination number and the unique response Roman domination number

Cited in

(12)

• On the signed Roman \(k\)-domination: complexity and thin torus graphs
• Improved integer linear programming formulation for weak Roman domination problem
• A note on Roman domination of digraphs
• Graphs with equal domination and covering numbers
• Trees with equal Roman \{2\}-domination number and independent Roman \{2\}-domination number
• On the total and strong version for Roman dominating functions in graphs
• A note on total co-independent domination in trees
• Constructive characterizations concerning weak Roman domination in trees
• Varieties of Roman Domination
• Extremal problems on weak Roman domination number
• On two open problems concerning weak Roman domination in trees
• Trees with equal strong Roman domination number and Roman domination number

This page was built for publication: Strong equality of Roman and weak Roman domination in trees

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