×

Roman domination in oriented trees. (English) Zbl 1468.05098

Summary: Let \(D=(V,A)\) be a digraph of order \(n= |V|\). A Roman dominating function of a digraph \(D\) is a function \(f: V \rightarrow \{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)= \sum_{u \in 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 \(\gamma_R(D)\). In this paper, we characterize oriented trees \(T\) satisfying \(\gamma_R(T)+\Delta^+(T) = n+1\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] X. Chen, G. Hao, and Z. Xie, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019), 13-21. · Zbl 1401.05219
[2] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math 23 (2009), 1575-1586. · Zbl 1207.05135
[3] M. Kamaraj and V. Hemalatha, Directed Roman domination in digraphs, International Jour-nal of Combinatorial Graph Theory and Applications 4 (2011), 103-116.
[4] M. Kamaraj, P. Jakkammal, Roman domination in digraphs. Submitted.
[5] T. W. Haynes, S.T. Hedetniemi and M. A. Henning, Topics in domination in graphs, Springer (2020). · Zbl 1470.05008
[6] L. Ouldrabah, M. Blidia, and A. Bouchou, Extremal digraphs for an upper bound on the Roman domination number, J. Comb. Optim. 38 (2019), 667-679. · Zbl 1429.05157
[7] A. Poureidi, Total Roman domination for proper interval graphs. Electron. J. Graph Theory Appl. 8 (2) (2020), 401-413. · Zbl 1468.05218
[8] N.J. Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (2017), 1-6. · Zbl 1467.05190
[9] S.M. Sheikholeslami and L. Volkmann, The Romain Domination Number of a digraph, Acta Universitatis Apulenisis 27 (2011), 77-86. · Zbl 1265.05470
[10] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), 136-138.
[11] S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a graph, Elec-tron. J. Graph Theory Appl. 3 (1) (2015), 85-93. · Zbl 1467.05099
[12] E. Zhu and Z. Shao, Extremal problems on weak Roman domination number, Inform. Pro-cess. Lett. 138 (2018), 12-18. · Zbl 1391.05197
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.