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 -