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→{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 γ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≥3 with s(T) support vertices, then γoiR(T)≤min{5n6,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