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

Document Type : Original paper

Authors

1 Universitat Rovira i Virgili

2 University of Cadiz

Abstract

Given a graph G=(V,E) and a vertex v∈V, by N(v) we represent the open neighbourhood of v. Let f:V→{0,1,2} be a function on G. The weight of f is ω(f)=∑v∈Vf(v) and let Vi={v∈V: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∈V0, ∑u∈N(v)f(u)≥2. The Roman {2}-domination number, denoted by γ{R2}(G), is the minimum weight among all Roman {2}-dominating functions on G;

2) a Roman dominating function, if for every vertex v∈V0 there exists u∈N(v)∩V2. The Roman domination number, denoted by γR(G), is the minimum weight among all Roman dominating functions on G.

It is known that for any graph G, γ{R2}(G)≤γR(G). In this paper, we characterize the trees T that satisfy the equality above.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 95-107

Files

Share

How to cite

Statistics