Strong equality of Roman and weak Roman domination in trees

DOI10.1016/J.DAM.2016.03.004zbMATH Open1336.05098arXiv1507.04902OpenAlexW2242715086MaRDI QIDQ284830FDOQ284830

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

Publication date: 18 May 2016

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

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.

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

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

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)

Cites Work

• Defending the Roman Empire---a new strategy
• Bounds on weak Roman and 2-rainbow domination numbers
• Strong equality of domination parameters in trees
• Construction of trees and graphs with equal domination parameters
• Strong equality between the Roman domination and independent Roman domination numbers in trees
• Trees with strong equality between the roman domination number and the unique response Roman domination number
• A characterization of Roman trees
• Characterizations of trees with equal domination parameters
• Title not available (Why is that?)
• Paired-domination in graphs

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
• Trees with equal Roman \{2\}-domination number and independent Roman \{2\}-domination number
• Graphs with equal domination and covering numbers
• 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)