Domination by Union of Complete Graphs

Abstract

Let \(G\) be a graph with domination number \(\gamma(G)\). A dominating set \(S \subseteq V(G)\) has property \(\mathcal{UK}\) if all components of the subgraph it induces in \(G\) are complete. The union of complete graphs domination number of a graph \(G\), denoted \(\gamma_{uk}(G)\), is the minimum possible size of a dominating set of \(G\), which has property \(\mathcal{UK}\). Results on changing and unchanging of \(\gamma_{uk}(G)\) after vertex removal are presented. Also forbidden subgraph conditions sufficient to imply \(\gamma(G) = \gamma_{uk}(G)\) are given.