Total domination in $K_r$-covered graphs

Abstract

The inflation $G_{I}$ of a graph $G$ with $n(G)$ vertices and $m(G)$ edges is obtained from $G$ by replacing every vertex of degree $d$ of $G$ by a clique, which is isomorph to the complete graph $K_{d}$, and each edge $(x_{i},x_{j})$ of $G$ is replaced by an edge $(u,v)$ in such a way that $uin X_{i}$, $vin X_{j}$, and two different edges of $G$ are replaced by non-adjacent edges of $G_{I}$. The total domination number $gamma _{t}(G)$ of a graph $G$ is the minimum cardinality of a total dominating set, which is a set of<br />vertices such that every vertex of $G$ is adjacent to one vertex of it. A graph is $K_{r}$-covered if every vertex of it is contained in a clique $K_{r}$. Cockayne et al. in [Total domination in $K_{r}$-covered graphs, Ars Combin. textbf{71} (2004) 289-303]<br />conjectured that the total domination number of every $K_{r}$-covered graph with $n$ vertices and no $K_{r}$-component is at most $frac{2n}{r+1}.$ This conjecture has been proved only for $3leq rleq 6$. In this paper, we prove this conjecture for a big family of $K_{r}$-covered graphs.