On roman, global and restrained domination in graphs

DOI10.1007/S00373-010-0992-ZMaRDI QIDQ659738zbMATH OpenOpenAlexFDO

Authors Vadim Zverovich, Anush Poghosyan

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

global domination numberrestrained domination numberRoman domination number

Mathematics Subject Classification ID

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

Abstract: In this paper, we present new upper bounds for the global domination and Roman domination numbers and also prove that these results are asymptotically best possible. Moreover, we give upper bounds for the restrained domination and total restrained domination numbers for large classes of graphs, and show that, for almost all graphs, the restrained domination number is equal to the domination number, and the total restrained domination number is equal to the total domination number. A number of open problems are posed.

Recommendations

• Remarks on restrained domination and total restrained domination in graphs
• On the global Roman domination number in graphs
• Some progress on the restrained Roman domination
• Total restrained domination in graphs
• Bounds on the restrained Roman domination number of a graph

Cites work

• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Almost all Graphs have a Spanning Cycle
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Degree sequences of random graphs
• Domination in graphs with minimum degree two
• Factor domination in graphs
• scientific article; zbMATH DE number 4204392 (Why is no real title available?)
• scientific article; zbMATH DE number 3747186 (Why is no real title available?)
• scientific article; zbMATH DE number 3531438 (Why is no real title available?)
• On equality in an upper bound for the restrained and total domination numbers of a graph
• On the domination number of a random graph
• On the ratio of optimal integral and fractional covers
• Paths, Stars and the Number Three
• Roman domination in graphs.
• Total restrained domination in graphs with minimum degree two
• Transversal numbers of uniform hypergraphs

Cited in

(20)

• On the global Roman domination number in graphs
• Some new results on global dominating sets
• Global triple Roman dominating function
• On the global double Roman domination of graphs
• Global Roman domination in trees
• Weighted restrained domination in subclasses of planar graphs
• Roman domination in graphs
• Global domination
• The Roman domination number of some special classes of graphs - convex polytopes
• scientific article; zbMATH DE number 1529469 (Why is no real title available?)
• Global double Roman domination in graphs
• scientific article; zbMATH DE number 7509363 (Why is no real title available?)
• scientific article; zbMATH DE number 7276884 (Why is no real title available?)
• Global italian domination in graphs
• Linear programming approach for various domination parameters
• THE GLOBAL EQUITABLE DOMINATION IN GRAPHS
• The extended dominating sets in graphs
• Weighted domination models and randomized heuristics
• Hardness results of global Roman domination in graphs
• Global Roman domination in graphs

This page was built for publication: On roman, global and restrained domination in graphs

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