Minimal dominating sets of cardinality two in a graph (Q1355671)

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if for each \(x\in V(G)-S\) there exists a vertex \(y\in S\) adjacent to \(x\). A conjecture of H. B. Walikar, B. D. Acharya and E. Sampathkumar says that if the minimum degree of a graph is at least half the number of vertices, then any two adjacent vertices of the graph form a minimal dominating set. This conjecture is disproved. The paper also contains a characterization of graphs in which every pair of adjacent vertices forms a minimal dominating set and of graphs in which so does every pair of vertices.