Abstract
A Roman dominating function \( f \) on a graph \( G \) is a global Roman dominating function on \( G \), if \( f \) is also a Roman dominating function on \( \bar{G} \). The weight of a global Roman dominating function \( f \) is the value \( w(f) = \sum\nolimits_{x \in V(G)} {f(x)} \). The minimum weight of a global Roman dominating function on a graph \( G \) is called the global Roman domination number \( \gamma_{gR} (G) \) of \( G \). In this paper, we present upper bounds for \( \gamma_{gR} (G) \) in terms of order, diameter, and girth. We give necessary and sufficient conditions for a graph \( G \) with property \( \gamma_{gR} (G) = \gamma_{g} (G) + i \) for all \( i = 0,1, 2,3 \), where \( \gamma_{g} (G) \) is the global domination number of \( G \). We also describe all connected unicyclic graphs \( G \) for which \( \gamma_{gR} \left( G \right) - \gamma_{R} (G) \) is maximum.
Similar content being viewed by others
References
Amjadi J, Karami H, Sheikholeslami SM, Volkmann L (2013) The Roman game domination subdivision number of a graph. Trans Comb 2:1–13
Arumugam S, Hamid IS, Karuppasamy K (2010) Fractional global domination in graphs. Discuss Math Graph Theory 30:33–44
Atapour M, Sheikholeslami SM, Volkmann L (2015) Global Roman domination in trees. Graphs Comb 31:813–825
Brigham RC, Dutton RD (1990) Factor domination in graphs. Discrete Math 86:127–136
Chambers EW, Kinnersley B, Prince N, West DB (2009) Extremal problems for Roman domination. SIAM J Discrete Math 23:1575–1586
Cockayne EJ, Favaron O, Mynhardt CM (2003) Secure domination, weak Roman domination and forbidden subgraphs. Bull Inst Comb Appl 39:87–100
Cockayne EJ, Dreyer PA Jr, Hedetniemi SM, Hedetniemi ST (2004) Roman domination in graphs. Discrete Math 278:11–22
Delic D, Wang C (2014) The global connected domination in graphs. Ars Comb 114:105–110
Favaron O, Karami H, Sheikholeslami SM (2009) On the Roman domination number in graphs. Discrete Math 309:3447–3451
Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York
Haynes TW, Hedetniemi ST, Slater PJ (1998b) Domination in graphs: advanced topics. Marcel Dekker Inc., New York
Henning MA (2002) A characterization of Roman trees. Discuss Math Graph Theory 22:225–234
Henning MA (2003) Defending the Roman Empire from multiple attacks. Discrete Math 271:101–115
Kulli VR, Janakiram B (1996) The total global domination number of a graph. India J Pure Appl Math 27:537–542
Mobaraky BP, Sheikholeslami SM (2008) Bounds on Roman domination numbers of graphs. Mat Vesnik 60:247–253
Ore O (1962) Theory of graphs. Am Math Soc Colloq Publ, 38
Paulraj Joseph J, Arumugam S (1995) Domination in graphs. Internat J Manag Syst 11:177–182
Payan C, Xuong NH (1982) Domination-balanced graphs. J Graph Theory 6:23–32
ReVelle CS, Rosing KE (2000) Defendens imperium romanum: a classical problem in military strategy. Am Math Mon 107:585–594
Sampathkumar E (1989) The global domination number of a graph. J Math Phys Sci 23:377–385
Sheikholeslami SM, Volkmann L (2011) The Roman domination number of a digraph. Acta Univ Apulensis Math Inf 27:77–86
Stewart I (1999) Defend the Roman empire. Sci Am 281:136–139
West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, USA
Zverovich V, Poghosyan A (1999) On Roman, global and restrained domination in graphs. Graphs Comb 27:755–768
Acknowledgments
The author is grateful to anonymous referees for their remarks and suggestions that helped improve the manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ahangar, H.A. On the Global Roman Domination Number in Graphs. Iran J Sci Technol Trans Sci 40, 157–163 (2016). https://doi.org/10.1007/s40995-016-0035-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40995-016-0035-6