Clique Domination in Graphs

Abstract

A set \(S\) of vertices in a graph \(G\) is a clique dominating set of \(G\) if \(S\) contains at least one vertex of every clique \(C\) of \(G\). The clique domination number \(\gamma_q(G)\) and the upper clique domination number \(\gamma_q(G)\) are, respectively, the minimum and maximum cardinalities of a minimal clique dominating set of \(G\). In this paper, we prove that the problem of computing \(\Gamma_q(G)\) is NP-complete even for split graphs and the problem of computing \(\gamma_q(G)\) is NP-complete even for chordal graphs. In addition, for a block graph \(BG\) we show that the clique domination number is bounded above by the vertex independence number (\(\gamma_q(BG) \leq \beta(BG)\)) and give a linear algorithm for computing \(\gamma_q(BG)\).