آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 126 |
| تعداد مقالات | 1,591 |
| تعداد مشاهده مقاله | 1,765,761 |
| تعداد دریافت فایل اصل مقاله | 1,644,542 |
Outer independent Roman domination number of trees | ||
| Communications in Combinatorics and Optimization | ||
| دوره 6، شماره 2، اسفند 2021، صفحه 273-286 اصل مقاله (376.61 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27072.1191 | ||
| نویسندگان | ||
| Nasrin Dehgardi* 1؛ M Chellali2 | ||
| 1Sirjan University of Technology, Sirjan 78137, Iran | ||
| 2LAMDA-RO Laboratory, Department of Mathematics University of Blida B.P. 270, Blida, Algeria | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Outer independent Roman dominating function؛ outer independent Roman domination number؛ tree | ||
| مراجع | ||
|
[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.
| ||
|
آمار تعداد مشاهده مقاله: 826 تعداد دریافت فایل اصل مقاله: 1,221 |
||