top library bulletin
bar home editorial guideline content
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

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 Nordhaus-Gaddum type result.

2010 Mathematics Subject Classification: 05C69

Full text: PDF