Domination Using Induced Cliques in Graphs

Let \(G = (V, E)\) be a graph and let \(\mathcal{H}\) be a set of graphs. A set \(S \subseteq V\) is \(\mathcal{H}\)-independent if for all \(H \in \mathcal{H}\), \(\langle S \rangle\) contains no subgraph isomorphic to \(H\). A set \(S \subseteq V\) is an \(\mathcal{H}\)-dominating set of \(G\) if for every \(v \in V – S\), \(\langle S \cup \{v\} \rangle\) contains a subgraph containing \(v\) which is isomorphic to some \(H \in \mathcal{H}\).

The \(\mathcal{H}\)-domination number of a graph \(G\), denoted by \(\gamma_{\mathcal{H}}(G)\), is the minimum cardinality of an \(\mathcal{H}\)-dominating set of \(G\) and the \(\mathcal{H}\)-independent domination number of \(G\), denoted by \(i_{\mathcal{H}}(G)\), is the smallest cardinality of an \(\mathcal{H}\)-independent \(\mathcal{H}\)-dominating set of \(G\).

A sequence of positive integers \(a_2 \leq \cdots \leq a_m\) is said to be a domination sequence if there exists a graph \(G\) such that \(\gamma_{(K_k)}(G) = a_k\) for \(k = 2, \ldots, m\). In this paper, we find an upper bound for \(\gamma_{\mathcal{H}}(G)\) and show that the problems of computing \(\gamma_{\{K_n\}}\) and \(i_{\{K_n\}}\) are NP-hard. Finally, we characterize nondecreasing sequences of positive integers which are domination sequences, and provide a sufficient condition for equality of \(\gamma_{\{K_n\}}(G)\) and \(i_{\{K_n\}}(G)\).