Vertex Transversals that Dominate

Noga Alon, Michael R. Fellows, Donovan R. Hare

Research output: Contribution to journalArticle

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)21-31
Number of pages11
JournalJournal of Graph Theory
Volume21
Issue number1
DOIs
StatePublished - Jan 1996
Externally publishedYes

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