On trees with equal Roman domination and outer-independent Roman domination numbers

Document Type : Original paper

Authors

Azarbaijan Shahid Madani University

Abstract

A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) \to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. A Roman dominating function $f$ is called an outer-independent Roman dominating function (OIRDF) on $G$ if the set $\{v\in V\mid f(v)=0\}$ is independent. The (outer-independent) Roman domination number $\gamma_{R}(G)$ ($\gamma_{oiR}(G)$) is the minimum weight of an RDF (OIRDF) on $G$. Clearly for any graph $G$, $\gamma_{R}(G)\le \gamma_{oiR}(G)$. In this paper, we provide a constructive characterization of trees $T$ with $\gamma_{R}(T)=\gamma_{oiR}(T)$. 

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, A. Bahremandpour, S.M. Sheikholeslami, N.D. Soner, Z. Tahmasbzadehbaee, and L. Volkmann, Maximal Roman domination numbers in graphs, Util. Math. 103 (2017), 245–258.
[2] H. Abdollahzadeh Ahangar, M. Chellali, and V. Samodivkin, Outer independent Roman dominating functions in graphs, Int. J. Computer Math. 94 (2017), no. 12, 2547–2557.
[3] H. Abdollahzadeh Ahangar, T.W. Haynes, and J.C. Valenzuela-Tripodoro, Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc. 40 (2017), no. 4, 1443–1454.
[4] H. Abdollahzadeh Ahangar, M.A. Henning, C. Lőwenstein, Y. Zhao, and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), no. 2, 241–255.
[5] M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad, and M. Saied Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin. 52 (2012), 11–18.
[6] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[7] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016), 22–28.
[8] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[9] M.A. Henning and S.T. Hedetniemi, Defending the Roman empirea new strategy, Discrete Math. 266 (2003), no. 1-3, 239–251.
[10] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[11] S.M. Sheikholeslami and L. Volkmann, Signed Roman domination in digraphs, J. Comb. Optim. 30 (2015), no. 3, 456–467.
[12] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[13] L. Volkmann, Signed total Roman domination in graphs, J. Comb. Optim. 32 (2016), no. 3, 855–871.
[14] L. Volkmann, Signed total Roman domination in digraphs, Discus. Math. Graph Theory 37 (2017), no. 1, 261–272.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 185-199

Files

Share

How to cite

Statistics