×

The double Roman domatic number of a digraph. (English) Zbl 1446.05074

Summary: A double Roman dominating function on a digraph \(D\) with vertex set \(V (D)\) is defined in [G. Hao et al., Bull. Malays. Math. Sci. Soc. (2) 42, No. 5, 1907–1920 (2019; Zbl 1419.05091)] as a function \(f : V (D) \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then the vertex \(v\) must have at least two in-neighbors assigned 2 under \(f\) or one in-neighbor \(w\) with \(f(w) = 3\), and if \(f(v) = 1\), then the vertex \(v\) must have at least one in-neighbor \(u\) with \(f(u) \geq 2\). A set \(\{f_1, f_2, \dots, f_d \}\) of distinct double Roman dominating functions on \(D\) with the property that \(\sum\nolimits_{i = 1}^d f_i (v) \le 3\) for each \(v \in V (D)\) is called a double Roman dominating family (of functions) on \(D\). The maximum number of functions in a double Roman dominating family on \(D\) is the double Roman domatic number of \(D\), denoted by \(d_{\mathrm{dR}}(D)\). We initiate the study of the double Roman domatic number, and we present different sharp bounds on \(d_{\mathrm{dR}}(D)\). In addition, we determine the double Roman domatic number of some classes of digraphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity

Citations:

Zbl 1419.05091
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Atapour, M. Chellali and S.M. Sheik-holeslami, Double Roman trees, Ars Combin., to appear. · Zbl 1463.05389
[2] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A Sci. (2018), in press. doi:10.1007/s40995-018-0535-7
[3] H. Abdollahzadeh Ahangar, M. Chellali and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017) 1-7. doi:10.1016/j.dam.2017.06.014 · Zbl 1372.05153
[4] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23-29. doi:10.1016/j.dam.2016.03.017 · Zbl 1348.05146
[5] G. Hao, X. Chen and L. Volkmann, Double Roman domination in digraphs, Bull. Malays. Math. Sci. Soc. (2017), in press. doi:10.1007/s40840-017-0582-9 · Zbl 1419.05091
[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). · Zbl 0890.05002
[7] N. Jafari Rad and H. Rahbani, Some progress on double Roman domination in graphs, Discuss. Math. Graph Theory, in press. doi:10.7151/dmgt.2069 · Zbl 1401.05224
[8] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175-177. doi:10.2307/2306658 · Zbl 0070.18503
[9] L. Volkmann, The double Roman domatic number of a graph, J. Combin. Math. Combin. Comput. 104 (2018) 205-215. · Zbl 1390.05181
[10] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983) 145-147. · Zbl 0516.05032
[11] X. Zhang, Z. Li, H. Jiang and Z. Shao, Double Roman domination in trees, Inform. Process. Lett. 134 (2018) 31-34. doi:10.1016/j.ipl.2018.01.004 · Zbl 1476.05162
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.