Domination graphs: Examples and counterexamples (Q5936465)

A domination graph is a graph \(G\) with the property that every induced subgraph \(H\) of \(G\) contains a pair of vertices \(x\), \(y\) such that in \(H\) the open neighbourhood of \(x\) is a subset of the closed neighbourhood of \(y\). Dahlhaus et al. have described an algorithm called the special quadratic consensus method. For a given graph \(G\) this algorithm returns TRUE, if \(G\) is a domination graph. The authors also conjecture that conversely the answer TRUE means that \(G\) is a domination graph. The present paper gives a counterexample. Further special classes of graphs, namely trapezoid graphs and tolerance graphs, are considered and proved to be domination graphs. Also the generalized join decomposability of graphs is studied.