On roman, global and restrained domination in graphs

DOI10.1007/S00373-010-0992-ZzbMATH Open1234.05180OpenAlexW2085620810MaRDI QIDQ659738FDOQ659738

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 numberRoman domination numberrestrained 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

• 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?)
• 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
• 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

(19)

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

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)