For a simple undirected graph G with complement \(\overline{G}\) , the central graph C(G) is constructed by adding a path of length two edges between all pairs of non-adjacent vertices in \(\overline{G}\) . In this work, utilizing the notion of central graphs, we provide a novel classification scheme for all simple undirected graphs based upon the existence of a minimum cardinality vertex cover that concomitantly serves as a dominating set in the complement. In particular, letting \(\gamma (H)\) be the domination number and \(\tau (H)\) be the vertex cover number for an arbitrary graph H, we show that either \(\gamma (C(G))=\tau (G)\) or \(\gamma (C(G))=\tau (G)+1\) . Here, with one well-characterized set of exceptions, \(\gamma (C(G))=\tau (G)\) holds if and only if some vertex cover for G is a dominating set for \(\overline{G}\) . In addition, we explicitly characterize the domination number of the central graph for a variety of graph classes, and show that it is NP-hard both to compute \(\gamma (C(G))\) and to decide whether \(\gamma (C(G))=\tau (G)\) or \(\gamma (C(G))=\tau (G)+1\) . Finally, we establish that it is NP-hard to decide if some open neighborhood in a graph is a minimum cardinality vertex cover, and discuss the implications of this result for a generalization of the art gallery visibility problem.
