Vertex transversals that dominate
Noga Alon, Michael R. Fellows, Donovan R. Hare · Journal of Graph Theory · 1996
For any graph, there is a largest integer k such that given any partition of the vertex set with at most k elements in each class of the partition, there is transversal of the partition that is a dominating set in the graph. Some basic results about this parameter, the partition domination number, are obtained. In particular, it is shown that its value is 2 for the two-dimensional infinite grid, and that determining whether a given vertex partition admits a dominating transversal is NP-complete, even for a graph which is a simple path. The existence of various dominating transversals in certain partitions in regular graphs is studied as well. © 1996 John Wiley & Sons, Inc.