Roman domination in oriented trees
Abstract
Let D=(V,A) be a digraph of order n = |V|. A Roman dominating function of a digraph D is a function f : V → {0,1,2} such that every vertex u for which f(u) = 0 has an in-neighbor v for which f(v) = 2. The weight of a Roman dominating function is the value f(V)=∑u∈V f(u). The minimum weight of a Roman dominating function of a digraph D is called the Roman domination number of D, denoted by γR(D). In this paper, we characterize oriented trees T satisfying γR(T)+Δ+(T) = n+1.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.9
References
E.J. Cockayne, P.M.Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004), 11--22.
X. Chen, G. Hao, Z. Xie, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019), 13--21.
E.W. Chambers, B. Kinnersley, N. Prince, D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math 23 (2009), 1575--1586.
M. Kamaraj and V. Hemalatha, Directed Roman domination in digraphs, International Journal of Combinatorial Graph
Theory and Applications 4 (2011), 103--116.
M. Kamaraj, P. Jakkammal, Roman domination in Digraphs. Submitted.
T. W. Haynes, S.T. Hedetniemi and M. A. Henning, Topics in domination in graphs, Springer (2020).
L. Ouldrabah, M. Blidia, A. Bouchou, Extremal digraphs for an upper bound on the Roman domination number, J. Comb. Optim. 38 (2019), 667--679.
A. Poureidi, Total Roman domination for proper interval graphs. Electron. J. Graph Theory Appl 8 (2) (2020), 401--413.
N. J. Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (2017), 1--6.
S.M. Sheikholeslami and L. Volkmann, The Romain Domination Number of a Digraph, Acta Universitatis Apulenisis 27 (2011), 77--86.
I. Stewart, Defend the Roman Empire!, Sci. Am. 281 (1999), 136--138.
S.M. Sheikholeslami and L. Volkmann,The signed Roman domatic number of a graph, Electron. J. Graph Theory Appl. 3 (1) (2015), 85--93.
E. Zhu, Z. Shao, Extremal problems on weak Roman domination number, Inform. Process. Lett. 138 (2018), 12--18.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.