Online citations, reference lists, and bibliographies.

On Roman, Global And Restrained Domination In Graphs

Vadim E. Zverovich, Anush Poghosyan
Published 2011 · Mathematics, Computer Science

Cite This
Download PDF
Analyze on Scholarcy
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.
This paper references
On Roman , global and restrained domination in graphs
A. Poghosyan (2011)
Factor domination in graphs. Discrete Math
R C Brigham (1990)
On the Domination Number of a Random Graph
B. Wieland (2001)
Transversal numbers of uniform hypergraphs. Graphs and Combin
N Alon (1990)
Domination number for almost every graph
K. Weber (1981)
Total restrained domination in graphs with minimum degree two
M. Henning (2008)
Defendens Imperium Romanum: A Classical Problem in Military Strategy
C. Revelle (2000)
On the ratio of optimal integral and fractional covers
L. Lovász (1975)
Roman domination in graphs
E. Cockayne (2004)
On equality in an upper bound for the restrained and total domination numbers of a graph
P. Dankelmann (2007)
Paths, Stars and the Number Three
B. Reed (1996)
Algorithms for Vertex Partitioning Problems on Partial k-Trees
J. Telle (1997)
Transversal numbers of uniform hypergraphs
N. Alon (1990)
The global domination number of a graph
E. Sampathkumar (1989)
Domination in graphs with minimum degree two
W. McCuaig (1989)
Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices
V. I. Arnautov (1974)
Degree sequences of random graphs, Discrete Math
B Bollobás (1981)
The Probabilistic Method
N. Alon (1992)
B. Reed (1996)
Sur le nombre d’absorption d’un graphe simple
C. Payan (1975)
Almost all graphs have a spanning cycle
John W. Moon (1972)
Degree sequences of random graphs
B. Bollobás (1981)
Defend the Roman Empire
I. Stewart (1999)
Factor domination in graphs
Robert C. Brigham (1990)

This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar