$k$-Tuple Total Domination in Inflated Graphs


Adel P. Kazemi




The inflation or inflated graph $G_I$ of a graph $G$ with $n$ vertices is obtained from $G$ by replacing every vertex $x_i$ of degree $d(x_i)$ of $G$ by a clique $X_i$, which is isomorphic to the complete graph $K_{d(x_i)}$, and each edge $(x_i,x_j)$ of $G$ is replaced by an edge $(u,v)$ in such a way that $u \in X_i$, $v \in X_j$, and two different edges of $G$ are replaced by non-adjacent edges of $G_I$. For integer $k\geq1$, the $k$-tuple total domination number $\gamma_{\times kt}(G)$ of $G$ is the minimum cardinality of a $k$-tuple total dominating set of $G$, which is a set of vertices in $G$ such that every vertex of $G$ is adjacent to at least $k$ vertices in it. For existing this number, must the minimum degree of $G$ be at least $k$. Henning and Kazemi in [Total domination in inflated graphs, Discrete Applied Mathematics 160 (2012) 164-169] have studied the $k$-tuple total domination number of inflated graphs, when $k=1$. Here, we continue their studying when $k\geq 2$. First we prove $nk\leq\gamma_{\times k,t}(G_I)\leq n(k+1)-1$ when $\delta (G) \geq k+1$, and then we characterize graphs $G$ that the $k$-tuple total domination number number of $G_I$ is either $nk$ or $nk+1$. Also we find some bounds for this number in the inflated graph $G_I$, when $G$ has a cut-edge $e$ or a cut-vertex $v$, in terms of the $k$-tuple total domination number of the inflation of the components of $G-e$ or of the $v$-components of $G-v$, respectively. Finally, we calculate this number for the inflation of some graphs.