A characterization of trees with equal Roman {2}-domination and Roman domination numbers

Cabrera Martinez, Abel; Gonzalez Yero, Ismael

doi:10.22049/cco.2019.26364.1103

تعداد نشریات	5
تعداد شماره‌ها	116
تعداد مقالات	1,317
تعداد مشاهده مقاله	1,319,038
تعداد دریافت فایل اصل مقاله	1,234,915

	A characterization of trees with equal Roman {2}-domination and Roman domination numbers
Communications in Combinatorics and Optimization
مقاله 3، دوره 4، شماره 2، اسفند 2019، صفحه 95-107 اصل مقاله (383.97 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2019.26364.1103
نویسندگان
Abel Cabrera Martinez¹؛ Ismael Gonzalez Yero^* ²
¹Universitat Rovira i Virgili
²University of Cadiz
چکیده
Given a graph $G=(V,E)$ and a vertex $v \in V$, by $N(v)$ we represent the open neighbourhood of $v$. Let $f:V\rightarrow \{0,1,2\}$ be a function on $G$. The weight of $f$ is $\omega(f)=\sum_{v\in V}f(v)$ and let $V_i=\{v\in V \colon f(v)=i\}$, for $i=0,1,2$. The function $f$ is said to be 1) a Roman $\{2\}$-dominating function, if for every vertex $v\in V_0$, $\sum_{u\in N(v)}f(u)\geq 2$. The Roman $\{2\}$-domination number, denoted by $\gamma_{\{R2\}}(G)$, is the minimum weight among all Roman $\{2\}$-dominating functions on $G$; 2) a Roman dominating function, if for every vertex $v\in V_0$ there exists $u\in N(v)\cap V_2$. The Roman domination number, denoted by $\gamma_R(G)$, is the minimum weight among all Roman dominating functions on $G$. It is known that for any graph $G$, $\gamma_{\{R2\}}(G)\leq \gamma_R(G)$. In this paper, we characterize the trees $T$ that satisfy the equality above.
کلیدواژه‌ها
Roman ${2}$-domination؛ $2$-rainbow domination؛ Roman domination؛ tree

مراجع
[1] J.D. Alvarado, S. Dantas, and D. Rautenbach, Relating 2-rainbow domination to Roman domination, Discuss. Math. Graph Theory 37 (2017), no. 4, 953–961. [2] B. Brešar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225. [3] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae, Roman ${2}$-domination, Discrete Appl. Math. 204 (2016), 22–28. [4] 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. [5] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451. [6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998. [7] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002), no. 2, 325–334. [8] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), 557–564. [9] W.F. Klostermeyer and G. MacGillivray, Roman, Italian, and 2-domination, Manuscript (2016). [10] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012), no. 7, 1386–1391. [11] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138. [12] I.G. Yero and J.A. Rodríguez-Velázquez, Roman domination in cartesian product graphs and strong product graphs, Appl. Anal. Discrete Math. 7 (2013), no. 2, 262–274.
آمار تعداد مشاهده مقاله: 1,250 تعداد دریافت فایل اصل مقاله: 1,195

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

A characterization of trees with equal Roman {2}-domination and Roman domination numbers