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)\to \{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)\ge 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_{dR}(G)$ of $G$.

A set $\{f_1,f_2, \dots,f_d\}$ of distinct double Roman dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 3$ for each $v\in 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 $\gamma_{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