




Volume 36 • Number 1 • 2013 

•
On the Total $\{k\}$Domination and Total $\{k\}$Domatic Number of Graphs
H. Aram, S. M. Sheikholeslami and L. Volkmann
Abstract.
For a positive integer $k$, a {\em total $\{k\}$dominating function} of a graph $G$ without isolated vertices is a function $f$ from the vertex set $V(G)$ to the set $\{0,1,2,\ldots,k\}$ such that for any vertex $v\in V(G)$, the condition $\sum_{u\in N(v)}f(u)\ge k$ is fulfilled, where $N(v)$ is the open neighborhood of $v$. The {\em weight} of a total $\{k\}$dominating function $f$ is the value $\omega(f)=\sum_{v\in V}f (v)$. The {\em total $\{k\}$domination number}, denoted by $\gamma_t^{\{k\}}(G)$, is the minimum weight of a total $\{k\}$dominating function on $G$. A set $\{f_1,f_2,\ldots,f_d\}$ of total $\{k\}$dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le k$ for each $v\in V(G)$, is called a {\em total $\{k\}$dominating family} (of functions) on $G$. The maximum number of functions in a total $\{k\}$dominating family on $G$ is the {\em total $\{k\}$domatic number} of $G$, denoted by $d_t^{\{k\}}(G)$. Note that $d_t^{\{1\}}(G)$ is the classic total domatic number $d_t(G)$. In this paper, we present bounds for the total $\{k\}$domination number and total $\{k\}$domatic number. In addition, we determine the total $\{k\}$domatic number of cylinders and we give a NordhausGaddum type result.
2010 Mathematics Subject Classification: 05C69
Full text: PDF








