Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: 4-uniform hypergraph

Sortuj według:

Ogranicz wyniki do:

Hypergraphs with large transversal number and with edge sizes at least four

100%

Henning M., Löwenstein C.

Open Mathematics

2012

tom 10

nr 3

1133-1140

Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.

Ograniczanie wyników

1 Open Mathematics

1 Henning M.

1 Löwenstein C.

1 2012

Wyniki wyszukiwania

Hypergraphs with large transversal number and with edge sizes at least four