### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 21-31 |

Number of pages | 11 |

Journal | Journal of Graph Theory |

Volume | 21 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1996 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology

## Fingerprint Dive into the research topics of 'Vertex Transversals that Dominate'. Together they form a unique fingerprint.

## Cite this

Alon, N., Fellows, M. R., & Hare, D. R. (1996). Vertex Transversals that Dominate.

*Journal of Graph Theory*,*21*(1), 21-31. https://doi.org/10.1002/(SICI)1097-0118(199601)21:1<21::AID-JGT3>3.0.CO;2-O