On the Total $\{k\}$-Domination and Total $\{k\}$-Domatic Number of Graphs

H. Aram ; S. M. Sheikholeslami ; L. Volkmann

Bulletin of the Malaysian Mathematical Society, Tome 36 (2013) no. 1

Résumé

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.

Détail

Classification : 05C69