Abstract
A function \(f:V(G)\rightarrow \{0,1,2\}\) on graph \(G=(V(G),E(G))\) satisfying the condition that every vertex \(u\) for which \(f(u)=0\) is adjacent at least one vertex \(v\) for which \(f(v)=2\) is a Roman dominating function (RDF). The weight of an RDF is the sum of its function value over all vertices. The Roman domination number of \(G\), denoted by \(\gamma _{R}(G)\), is the minimum weight of an RDF on \(G\). An RDF \(f:V(G)\rightarrow \{0,1,2\}\) is called a global Roman dominating function (GRDF) if \(f\) is also an RDF of the complement \(\overline{G}\) of \(G\). The global Roman domination number of \(G\), denoted by \(\gamma _{gR}(G)\), is the minimum weight of a GRDF on \(G\). In this paper, we initiate global Roman domination number and study the basic properties of global Roman domination of a graph. Then we present some sharp bounds for global Roman domination number. In particular, we prove that for any tree of order \(n\ge 4\), \(\gamma _{gR}(T)\le \gamma _{R}(T)+2\) and we characterize all trees with \(\gamma _{gR}(T)=\gamma _{R}(T)+2\) and \(\gamma _{gR}(T)= \gamma _{R}(T)+1\).
Similar content being viewed by others
References
Arumugam, S., Hamid, I.S., Karuppasamy, K.: Fractional global domination in graphs. Discuss. Math. Graph Theory 30, 33–44 (2010)
Chambers, E.W., Kinnersley, B., Prince, N., West, D.B.: Extremal problems for Roman domination. SIAM J. Discrete Math. 23, 1575–1586 (2009)
Cockayne, E.J., Dreyer Jr, P.M., Hedetniemi, S.M., Hedetniemi, S.T.: On Roman domination in graphs. Discrete Math. 278, 11–22 (2004)
Delic̀ D., Wang, C. P.: The global connected domination in graphs. Ars Combin. (to appear)
Kulli, V.R., Janakiram, B.: The total global domination number of a graph. India J. Pure Appl. Math. 27, 537–542 (1996)
Revelle, C.S., Rosing, K.E.: Defendens imperium romanum: a classical problem in military strategy. Am. Math. Monthly 107, 585–594 (2000)
Sampathkumar, E.: The global domination number of a graph. J. Math. Phys. Sci. 23, 377–385 (1989)
Stewart, I.: Defend the Roman Empire. Sci. Am. 281, 136–139 (1999)
West, D. B.: Introduction to Graph Theory. Prentice-Hall Inc, Upper Saddle River (2000)
Zverovich, V., Poghosyan, A.: On Roman, global and restrained domination in graphs. Graphs Combin. 27, 755–768 (2011)
Acknowledgments
The authors would like to thank anonymous referees for their helpful suggestions and comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Atapour, M., Sheikholeslami, S.M. & Volkmann, L. Global Roman Domination in Trees. Graphs and Combinatorics 31, 813–825 (2015). https://doi.org/10.1007/s00373-014-1415-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-014-1415-3
Keywords
- Roman dominating function
- Roman domination number
- Global Roman dominating function
- Global Roman domination number