Covering a hypergraph of subgraphs

Noga Alon

doi:10.1016/S0012-365X(02)00427-2

Covering a hypergraph of subgraphs

Noga Alon

Research output: Contribution to journal › Conference article › peer-review

13 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 τ(ℋ) ≤ 2d²v(ℋ). 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 language	English (US)
Pages (from-to)	249-254
Number of pages	6
Journal	Discrete Mathematics
Volume	257
Issue number	2-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00427-2
State	Published - Nov 28 2002
Externally published	Yes
Event	Kleitman and Combinatorics: A Celebration - Cambridge, MA, United States Duration: Aug 16 1990 → Aug 18 1990

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00427-2

Cite this

@article{38b2eca0478b40a48d48e37afa2fed77,

title = "Covering a hypergraph of subgraphs",

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.",

author = "Noga Alon",

note = "Funding Information: 1Research supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. E-mail address: [email protected] (N. Alon).; Kleitman and Combinatorics: A Celebration ; Conference date: 16-08-1990 Through 18-08-1990",

year = "2002",

month = nov,

day = "28",

doi = "10.1016/S0012-365X(02)00427-2",

language = "English (US)",

volume = "257",

pages = "249--254",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2-3",

}

TY - JOUR

T1 - Covering a hypergraph of subgraphs

AU - Alon, Noga

N1 - Funding Information: 1Research supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. E-mail address: [email protected] (N. Alon).

PY - 2002/11/28

Y1 - 2002/11/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=31244435891&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=31244435891&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00427-2

DO - 10.1016/S0012-365X(02)00427-2

M3 - Conference article

AN - SCOPUS:31244435891

SN - 0012-365X

VL - 257

SP - 249

EP - 254

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2-3

T2 - Kleitman and Combinatorics: A Celebration

Y2 - 16 August 1990 through 18 August 1990

ER -

Covering a hypergraph of subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this