Online citations, reference lists, and bibliographies.

Extremal Problems For Roman Domination

Erin W. Chambers, Bill Kinnersley, N. Prince, D. West
Published 2009 · Mathematics, Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
A Roman dominating function of a graph $G$ is a labeling $f\colon\,V(G)\to\{0,1,2\}$ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number $\gamma_R(G)$ of $G$ is the minimum of $\sum_{v\in V(G)}f(v)$ over such functions. Let $G$ be a connected $n$-vertex graph. We prove that $\gamma_R(G)\leq4n/5$, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for $\gamma_R(G)+\gamma_R(\overline{G})$ and $\gamma_R(G)\gamma_R(\overline{G})$, improving known results for domination number. We prove that $\gamma_R(G)\leq8n/11$ when $\delta(G)\geq2$ and $n\geq9$, and this is sharp.
This paper references
10.1016/S0012-365X(03)00040-2
Defending the Roman Empire from multiple attacks
M. Henning (2003)
Gaddum . On complementary graphs
E. A. Nordhaus (2005)
Hedetniemi . Roman domination in graphs
P. A. Dreyer (2004)
10.1016/j.disc.2003.06.004
Roman domination in graphs
E. Cockayne (2004)
A unified approach to Roman domination problems on interval graphs , preprint
A. P. Burger
Dirac. M inimally 2-connected graphs
G A. (1967)
10.7151/dmgt.1178
A characterization of Roman trees
M. Henning (2002)
Secure domination
E. J. Cockayne (2003)
The algorithmic complexity of Roman domination
E J Cockayne
Protection of a graph
S. T. Hedetniemi T. W. Haynes (2005)
Finite Order Domination in Graphs
A. Burger (2003)
Roman domination on graphs with minimum degree at least 3, preprint
G J Chang
Secure domination, weak Roman domination and forbidden subgraphs
E J Cockayne (2003)
Sur le nombre d'absorption d'un graphe simple, in Colloque sur la Théorie des Graphes
C Payan (1974)
10.1016/j.disc.2006.06.018
A note on Roman domination in graphs
H. Xing (2006)
The algorithmic complexity of Roman domination
E J Cockayne
10.2307/2306658
On Complementary Graphs
E. A. Nordhaus (1956)
Sur le nombre d'absorption d'un graphe simple, in Colloque sur la Théorie des Graphes
C Payan (1974)
Sur le nombre d ’ absorption d ’ un graphe simple , in Colloque sur la Théorie des Graphes ( Paris , 1974 )
C. Payan. (1989)
10.1515/9783111576855-015
J
Seguin Hen (1824)
10.1515/crll.1967.228.204
Minimally 2-connected graphs.
G. Dirac (1967)
Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple
F. Jaeger (1972)
Secure domination , weak Roman domination and forbidden subgraphs
W. R. Gründlingh (2003)
10.1007/11604686_10
Roman Domination over Some Graph Classes
M. Liedloff (2005)
Protection of a graph
E J Cockayne (2005)
10.1201/9781482246582
Fundamentals of domination in graphs
T. Haynes (1998)
Sur le nombre d’absorption d’un graphe simple
C. Payan (1975)
Defend the Roman Empire! Sci
I. Stewart (1999)
Masters Thesis
C.-H. Liu (2009)
10.1016/S0012-365X(02)00811-7
Defending the Roman Empire--A new strategy
M. Henning (2003)
Roman Domination Number and Domination Number of a Tree
Song (2006)
A unified approach to Roman domination problems on interval graphs, preprint
G J Chang
10.1002/jgt.3190130610
Domination in graphs with minimum degree two
W. McCuaig (1989)
Protection of a graph
E J Cockayne (2005)
Secure domination, weak Roman domination and forbidden subgraphs
E J Cockayne (2003)
Secure domination , weak Roman domination and forbidden subgraphs
P. J. P. Grobler (2003)
Protection of a graph
T. W. Haynes
Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices
V. I. Arnautov (1974)
Can you protect the Roman Empire
C. S. ReVelle (1997)
10.1016/0020-0190(88)90091-9
A Unified Approach to Domination Problems on Interval Graphs
G. Ramalingam (1988)
10.1038/SCIENTIFICAMERICAN1299-136
Defend the Roman Empire
I. Stewart (1999)



This paper is referenced by
Italian Domination on Ladders and Related Products
Bradley M. Gardner (2018)
10.1007/S10878-019-00408-Y
On perfect Roman domination number in trees: complexity and bounds
Mahsa Darkooti (2019)
10.1007/978-3-642-45278-9_8
Exact Algorithms for Weak Roman Domination
Mathieu Chapelle (2013)
10.7151/dmgt.2091
On The Co-Roman Domination in Graphs
Xinmiao Liu (2019)
10.1016/j.dam.2017.09.015
Exact algorithms for weak Roman domination
Mathieu Chapelle (2018)
Graphs with Large Roman Domination Number
Ahangar (2017)
10.1007/s00373-011-1040-3
k-Domination and k-Independence in Graphs: A Survey
M. Chellali (2012)
10.1007/s10878-017-0157-6
Weak {2}-domination number of Cartesian products of cycles
Zepeng Li (2018)
10.7151/dmgt.2142
Extremal Graphs for a Bound on the Roman Domination Number
Mostafa Blidia (2020)
10.1142/S1793557120501107
Total Roman domatic number of a graph
J. Amjadi (2019)
Total Roman domination number of trees
L. Volkmann (2017)
ON ROMAN DOMINATION OF DIGRAPHS
Guoliang Hao (2019)
10.1016/j.dam.2016.01.021
Averaging 2-rainbow domination and Roman domination
José D. Alvarado (2016)
10.5556/J.TKJM.47.2016.2035
Twin signed total domination numbers in directed graphs
M. Atapour (2018)
10.1016/J.DAM.2018.06.008
Total Roman domination in the lexicographic product of graphs
Nicolas Campanelli (2019)
10.7151/dmgt.1975
On The Roman Domination Stable Graphs
Majid Hajian (2017)
10.1007/s41980-019-00274-8
Independent Double Roman Domination in Graphs
Hamidreza Maimani (2020)
10.3390/math8030349
Further Results on the Total Roman Domination in Graphs
Abel Cabrera Martínez (2020)
10.1016/j.disc.2011.12.021
Upper bounds on Roman domination numbers of graphs
C. Liu (2012)
10.1007/978-3-319-78825-8_3
Extremal Kernelization: A Commemorative Paper
Henning Fernau (2017)
10.1007/s10878-010-9352-4
The total {k}-domatic number of a graph
Seyed Mahmoud Sheikholeslami (2012)
10.7151/dmgt.1703
The Distance Roman Domination Numbers of Graphs
Hamideh Aram (2013)
On the Roman Bondage Number of Graphs on surfaces
Vladimir Samodivkin (2014)
10.1016/j.dam.2016.12.013
On the strong Roman domination number of graphs
M. P. Álvarez-Ruiz (2017)
10.1137/080733085
Roman Domination on 2-Connected Graphs
C. Liu (2012)
ROMAN EDGE k-DOMINATION IN GRAPHS
L. Asgharsharghi (2016)
10.7151/dmgt.2067
A Note on Roman Domination of Digraphs
Xiaodan Chen (2019)
10.1007/s10878-017-0158-5
Nordhaus–Gaddum bounds for total Roman domination
J. Amjadi (2018)
10.22049/CCO.2019.26419.1107
A note on the Roman domatic number of a digraph
L. Volkmann (2020)
10.1016/j.dam.2014.07.030
The signed Roman k-domatic number of a graph
Lutz Volkmann (2015)
10.1007/s00373-014-1415-3
Global Roman Domination in Trees
M. Atapour (2015)
10.5556/J.TKJM.48.2017.2240
Signed strong Roman domination in graphs
Seyed Mahmoud Sheikholeslami (2017)
See more
Semantic Scholar Logo Some data provided by SemanticScholar