Dominating cliques in graphs (Q5925264)

A subset D of the vertex set V(G) of a graph G is called dominating, if for each vertex \(x\in V(G)-D\) there exists a vertex \(y\in D\) adjacent to x. If a dominating set induces a complete subgraph of G, it is called a dominating clique. Some existence theorems for dominating clique sets of small cardinalities are proved. The clique domination number of G is defined as the minimum cardinality of a dominating clique in G. It is compared with the domination number and with the independent domination number of G. An algorithm for finding a dominating clique is presented; it works in the time \(O(n^ 3)\), where n is the number of vertices. Further, the so-called threshold dimension of a graph is studied; this is the minimum number of subgraphs which cover all edges of the graph and none of which contains \(P_ 4\), \(C_ 4\) or \(2K_ 2\) as an induced subgraph.