×

Double Roman domination and domatic numbers of graphs. (English) Zbl 1384.05128

Summary: A double Roman dominating function on a graph \(G\) with vertex set \(V(G)\) is defined in [R. A. Beeler et al., Discrete Appl. Math. 211, 23–29 (2016; Zbl 1348.05146)] as a function \(f:V(G)\rightarrow\{0,1,2,3\}\) having the property that if \(f(v)=0\), then the vertex \(v\) must have at least two neighbors assigned 2 under \(f\) or one neighbor \(w\) with \(f(w)=3\), and if \(f(v)=1\), then the vertex \(v\) must have at least one neighbor \(u\) with \(f(u)\geq 2\). The weight of a double Roman dominating function \(f\) is the sum \(\sum_{v\in V(G)}f(v)\), and the minimum weight of a double Roman dominating function on \(G\) is the double Roman domination number \(\gamma_{\mathrm{dR}}(G)\) of \(G\). A set \(\{f_1,f_2,\ldots,f_d\}\) of distinct double Roman dominating functions on \(G\) with the property that \(\sum_{i=1}^df_i(v)\leq 3\) for each \(v\in V(G)\) is called in [L. Volkmann, “The double Roman domatic number of a graph”, J. Comb. Math. Comb. Comput. 104, 205–215 (2018)] a double Roman dominating family (of functions)on \(G\). The maximum number of functions in a double Roman dominating family on \(G\) is the double Roman domatic number of \(G\). In this note we continue the study the double Roman domination and domatic numbers. In particular, we present a sharp lower bound on \(\gamma_{\mathrm{dR}}(G)\), and we determine the double Roman domination and domatic numbers of some classes of graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1348.05146
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 apeear). · 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 dom ination number plus two, Iran. J. Sci. Technol. Trans. A Sci. (to apeear). · Zbl 1415.05128
[3] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1-7. · Zbl 1372.05153
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23-29. · Zbl 1348.05146
[5] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575-1586. · Zbl 1207.05135
[6] 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. · Zbl 1036.05034
[7] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. · Zbl 0890.05002
[8] N. Jafari Rad and H. Rahbani, Some progress on double Roman domination in graphs, Discuss. Math. Graph Theory (to apeear). · Zbl 1377.05143
[9] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585-594. · Zbl 1039.90038
[10] S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010), no. 10, 1295-1300. · Zbl 1193.05129
[11] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136-138.
[12] L. Volkmann, The double Roman domatic number of a graph, J. Combin. Math. Combin. Comput. 104 (2018), 205-215. · Zbl 1390.05181
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.