Total Domination in \(K_r\)-Covered Graphs

Abstract

A graph \(G\) is \(K_r\)-covered if each vertex of \(G\) is contained in a clique \(K_r\). Let \(\gamma(G)\) and \(\gamma_t(G)\) respectively denote the domination and the total domination number of \(G\). We prove the following results for any graph \(G\) of order \(n\):

If \(G\) is \(K_6\)-covered, then \(\gamma_t(G) \leq \frac{n}{3}\),

If \(G\) is \(K_r\)-covered with \(r = 3\) or \(4\) and has no component isomorphic to \(K_r\), then \(\gamma_t(G) \leq \frac{2n}{r+1}\),

If \(G\) is \(K_3\)-covered and has no component isomorphic to \(K_3\), then \(\gamma(G) + \gamma_t(G) \leq \frac{7n}{9}\).

Corollaries of the last two results are that every claw-free graph of order \(n\) and minimum degree at least \(3\) satisfies \(\gamma_t(G) \leq \frac{n}{2}\) and \(\gamma(G) + \gamma(G) \leq \frac{7n}{9}\). For general values of \(r\), we give conjectures which would generalise the previous results. They are inspired by conjectures of Henning and Swart related to less classical parameters \(\gamma_{K_r}\) and \(\gamma^t_{K_r}\).