Outer independent Roman domination number of trees

Document Type : Original paper

Authors

1 Sirjan University of Technology, Sirjan 78137, Iran

2 LAMDA-RO Laboratory, Department of Mathematics University of Blida B.P. 270, Blida, Algeria

Abstract

A Roman dominating function (RDF) on a graph $G=(V,E)$ is a function $f:V\rightarrow \{0,1,2\}$ such that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. An RDF $f$ is called an outer independent Roman dominating function (OIRDF) if the set of vertices assigned a $0$ under $f$ is an independent set. The weight of an OIRDF is the sum of its function values over all vertices, and the outer independent Roman domination number $\gamma _{oiR}(G)$ is the minimum weight of an OIRDF on $G$. In this paper, we show that if $T$ is a tree of order $n\geq 3$ with $s(T)$ support vertices, then $\gamma _{oiR}(T)\leq \min \{\frac{5n}{6},\frac{3n+s(T)}{4}\}.$ Moreover, we characterize the tress attaining each bound.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, and V. Samodivkin, Outer independent Roman dominating functions in graphs, Int. J. Comput. Math. 94 (2017), no. 12, 2547–2557.
[2] A. Cabrera Martínez, S. Cabrera García, A. Carrión García, and A.M. Grisales del Rio, On the outer-independent Roman domination in graphs, Symmetry 12 (2020), no. 11, ID: 1846.
[3] A. Cabrera Mart´ınez, D. Kuziak, and I.G. Yero, A constructive characterization of vertex cover Roman trees, Discuss. Math. Graph Theory 41 (2021), no. 1, 267–283.
[4] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, Haynes, T.W., Hedetniemi, S.T., Henning, M.A., Eds., Springer International Publishing, 2020, pp. 365–409.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, Haynes, T.W., Hedetniemi, S.T., Henning, M.A., Eds., Springer International Publishing, 2021.
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory (in press).
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Comb. Comput. (to appear).
[9] 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.
[10] N. Jafari Rad, F. Azvin, and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6, no. 1, 123–136.
[11] A. Poureidi, M. Ghaznavi, and J. Fathali, Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination, J. Comb. Optim., (in press).
[12] S.M. Sheikholeslami and S. Nazari-Moghaddam, On trees with equal Roman domination and outer-independent Roman domination numbers, Commun. Comb. Optim. 4 (2019), no. 2, 185–199.
 
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 273-286

Files

Share

How to cite

Statistics