Double Roman domination and domatic numbers of graphs

Document Type : Original paper

Author

RWTH Aachen University

Abstract

A double Roman dominating function on a graph G with vertex set V(G) is defined in cite{bhh} as a function f:V(G)→{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)≥2. The weight of a double Roman dominating function f is the sum ∑v∈V(G)f(v), and the minimum weight of a double Roman dominating function on G is the double Roman domination number γdR(G) of G.

A set {f1,f2,…,fd} of distinct double Roman dominating functions on G with the property that ∑i=1dfi(v)≤3 for each v∈V(G) is called 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 γdR(G), and we determine the double Roman domination and domatic numbers of some classes of graphs.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Atapour, M. Chellali, and S.M. Sheikholeslami, Double Roman trees, Ars Combin. (to apeear). 
[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. (to apeear).
[3] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[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.
[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.
[7] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[8] N. Jafari Rad and H. Rahbani, Some progress on double Roman domination in graphs, Discuss. Math. Graph Theory (to apeear).
[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.
[10] S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010), no. 10, 1295–1300.
[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.
Communications in Combinatorics and Optimization
Volume 3, Issue 1
June 2018
Pages 71-77

Files

Share

How to cite

Statistics