首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号