Covering a hypergraph of subgraphs

Research output: Contribution to journalConference article

12 Scopus citations

Abstract

Let G be a tree and let ℋ be a collection of subgraphs of G, each having at most d connected components. Let v(ℋ) denote the maximum number of members of ℋ no two of which share a common vertex, and let τ(ℋ) denote the minimum cardinality of a set of vertices of G that intersects all members of ℋ. It is shown that τ(ℋ) ≤ 2d2v(ℋ). A similar, more general result is proved replacing the assumption that G is a tree by the assumption that it has a bounded tree-width. These improve and extend results of various researchers.

Original languageEnglish (US)
Pages (from-to)249-254
Number of pages6
JournalDiscrete Mathematics
Volume257
Issue number2-3
DOIs
StatePublished - Nov 28 2002
Externally publishedYes
EventKleitman and Combinatorics: A Celebration - Cambridge, MA, United States
Duration: Aug 16 1990Aug 18 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Covering a hypergraph of subgraphs'. Together they form a unique fingerprint.

  • Cite this