TY - JOUR
T1 - Vertex Transversals that Dominate
AU - Alon, Noga
AU - Fellows, Michael R.
AU - Hare, Donovan R.
PY - 1996/1
Y1 - 1996/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0030552396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030552396&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1097-0118(199601)21:1<21::AID-JGT3>3.0.CO;2-O
DO - 10.1002/(SICI)1097-0118(199601)21:1<21::AID-JGT3>3.0.CO;2-O
M3 - Article
AN - SCOPUS:0030552396
SN - 0364-9024
VL - 21
SP - 21
EP - 31
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 1
ER -