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
Share
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)
10.37236/1581
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)
10.1016/j.disc.2007.04.039
Total restrained domination in graphs with minimum degree two
M. Henning (2008)
10.1080/00029890.2000.12005243
Defendens Imperium Romanum: A Classical Problem in Military Strategy
C. Revelle (2000)
10.1016/0012-365X(75)90058-8
On the ratio of optimal integral and fractional covers
L. Lovász (1975)
10.1016/j.disc.2003.06.004
Roman domination in graphs
E. Cockayne (2004)
10.1016/j.disc.2007.03.003
On equality in an upper bound for the restrained and total domination numbers of a graph
P. Dankelmann (2007)
10.1017/S0963548300002042
Paths, Stars and the Number Three
B. Reed (1996)
10.1137/S0895480194275825
Algorithms for Vertex Partitioning Problems on Partial k-Trees
J. Telle (1997)
10.1007/BF01787474
Transversal numbers of uniform hypergraphs
N. Alon (1990)
The global domination number of a graph
E. Sampathkumar (1989)
10.1002/jgt.3190130610
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)
10.1007/978-1-84628-970-5_13
The Probabilistic Method
N. Alon (1992)
Paths
B. Reed (1996)
Sur le nombre d’absorption d’un graphe simple
C. Payan (1975)
10.4153/cmb-1972-008-3
Almost all graphs have a spanning cycle
John W. Moon (1972)
10.1016/0012-365X(81)90253-3
Degree sequences of random graphs
B. Bollobás (1981)
10.1038/SCIENTIFICAMERICAN1299-136
Defend the Roman Empire
I. Stewart (1999)
10.1016/0012-365X(90)90355-L
Factor domination in graphs
Robert C. Brigham (1990)



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