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)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)ge 2$. The weight of a double Roman dominating function $f$ is the sum
$sum_{vin 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,ldots,f_d}$ of distinct double Roman dominating functions on $G$ with the property that
$sum_{i=1}^df_i(v)le 3$ for each $vin V(G)$ is called in cite{v} 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