Hypergraph families with bounded edge cover or transversal number |
| |
Authors: | A Gyárfás J Lehel |
| |
Institution: | (1) Computer and Automation Institute of the Hungarian Academy of Sciences, Kende u. 13-17, 1111 Budapest, Hungary |
| |
Abstract: | The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ
and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied
to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph
theoretic terms like the family where every subhypergraph has the Helly-property. |
| |
Keywords: | 05C 65 05 B 40 |
本文献已被 SpringerLink 等数据库收录! |
|