On upper transversals in 3-uniform hypergraphs

被引:0
作者
Henning, Michael A. [1 ]
Yeo, Anders [1 ,2 ]
机构
[1] Univ Johannesburg, Dept Pure & Appl Math, ZA-2006 Auckland Pk, South Africa
[2] Univ Southern Denmark, Dept Math & Comp Sci, Campusvej 55, DK-5230 Odense M, Denmark
基金
新加坡国家研究基金会;
关键词
INDEPENDENT DOMINATION; PARAMETERS;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. The upper transversal number Upsilon(H) of H is the maximum cardinality of a minimal transversal in H. We show that if H is a connected 3-uniform hypergraph of order n, then Upsilon(H) > 1.4855 3 root n - 2. For n sufficiently large, we construct infinitely many connected 3-uniform hypergraphs, H, of order n satisfying Upsilon(H) < 2.5199 3 root n. We conjecture that sup(n ->infinity) (inf Upsilon(H)/3 root n) = 3 root 16, where -F2, the infimum is taken over all connected 3-uniform hypergraphs H of order n.
引用
收藏
页数:9
相关论文
共 14 条
[1]  
Berge C., 1989, HYPERGRAPHS COMBINAT
[2]   GRAPH-THEORETIC PARAMETERS CONCERNING DOMINATION, INDEPENDENCE, AND IRREDUNDANCE [J].
BOLLOBAS, B ;
COCKAYNE, EJ .
JOURNAL OF GRAPH THEORY, 1979, 3 (03) :241-249
[3]  
Bujtás C, 2014, ELECTRON J COMB, V21
[4]   Transversals and domination in uniform hypergraphs [J].
Bujtas, Csilla ;
Henning, Michael A. ;
Tuza, Zsolt .
EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (01) :62-71
[5]   2 RELATIONS BETWEEN THE PARAMETERS OF INDEPENDENCE AND IRREDUNDANCE [J].
FAVARON, O .
DISCRETE MATHEMATICS, 1988, 70 (01) :17-20
[6]  
GIMBEL J, 1995, ARS COMBINATORIA, V39, P109
[7]   On the independent domination number of graphs with given minimum degree [J].
Glebov, NI ;
Kostochka, AV .
DISCRETE MATHEMATICS, 1998, 188 (1-3) :261-266
[8]   Independent domination in graphs: A survey and recent results [J].
Goddard, Wayne ;
Henning, Michael A. .
DISCRETE MATHEMATICS, 2013, 313 (07) :839-854
[9]  
Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
[10]  
Haynes TW., 1998, FUNDAMENTALS DOMINAT