Dominating cliques in graphs (Q5896554)

A set of vertices in a graph is called a dominating set if every vertex not in the set of adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The authors discuss various conditions that suffice to guarantee the existence of a dominating clique. Furthermore, a polynomial algorithm is presented that finds a dominating clique in finite connected graphs with no induced \(P_ 5\) or \(C_ 5\). Finally, a forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.