Graphs and Algorithms

A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let $\gamma_t(G)$ denote the total domination number of G. It has been conjectured that every Kr-covered graph of order n with no Kr-component satisﬁes $\gamma_t(G) \le \frac{2n}{r+1}$. We prove that this conjecture is true for r = 5 and 6.