Transversals and Independence in Linear Hypergraphs with Maximum Degree Two

被引:0
作者
Henning, Michael A. [1 ]
Yeo, Anders [1 ,2 ]
机构
[1] Univ Johannesburg, Dept Pure & Appl Math, Auckland Pk, ZA-2006 Johannesburg, South Africa
[2] Univ Southern Denmark, Dept Math & Comp Sci, Campusvej 55, DK-5230 Odense M, Denmark
基金
新加坡国家研究基金会;
关键词
Transversal; Hypergraph; Linear hypergraph; Strong independence; INTERSECTION-THEOREMS; FINITE SETS; GRAPHS; DOMINATION; NUMBER; MATCHINGS; SYSTEMS; SIZE;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For k >= 2, let H be a k-uniform hypergraph on n vertices and m edges. Let S be a set of vertices in a hypergraph H. The set S is a transversal if S intersects every edge of H, while the set S is strongly independent if no two vertices in S belong to a common edge. The transversal number, tau(H), of H is the minimum cardinality of a transversal in H, and the strong independence number of H, alpha(H), is the maximum cardinality of a strongly independent set in H. The hypergraph H is linear if every two distinct edges of H intersect in at most one vertex. Let H-k be the class of all connected, linear, k -uniform hypergraphs with maximum degree 2. It is known [European J. Combin. 36 (2014), 231-236] that if H E is an element of H-k, then (k +1)tau(H) <= n + m, and there are only two hypergraphs that achieve equality in the bound. In this paper, we prove a much more powerful result, and establish tight upper bounds on tau(H) and tight lower bounds on alpha(H) that are achieved for infinite families of hypergraphs. More precisely, if k >= 3 is odd and H is an element of H-k has n vertices and rn edges, then we prove that k(k(2) - 3)tau(H) <= (k - 2)(k +1)n+ (k - 1)(2)m+ k - 1 and k(k(2) - 3)alpha(H) >= (k(2) +k - 4)n -(k - 1)(2)m - (k - 1). Similar bounds are proven in the case when k >= 2 is even.
引用
收藏
页数:25
相关论文
共 30 条
[1]  
[Anonymous], 1986, MATCHING THEORY
[2]  
[Anonymous], 1995, Handbook of Combinatorics
[3]   A note on the edge cover number and independence number in hypergraphs [J].
Berger, Eli ;
Ziv, Ran .
DISCRETE MATHEMATICS, 2008, 308 (12) :2649-2654
[4]   The potential of greed for independence [J].
Borowiecki, Piotr ;
Goering, Frank ;
Harant, Jochen ;
Rautenbach, Dieter .
JOURNAL OF GRAPH THEORY, 2012, 71 (03) :245-259
[5]   Transversals and domination in uniform hypergraphs [J].
Bujtas, Csilla ;
Henning, Michael A. ;
Tuza, Zsolt .
EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (01) :62-71
[6]   SMALL TRANSVERSALS IN HYPERGRAPHS [J].
CHVATAL, V ;
MCDIARMID, C .
COMBINATORICA, 1992, 12 (01) :19-26
[7]   MATCHINGS AND TRANSVERSALS IN HYPERGRAPHS, DOMINATION AND INDEPENDENCE IN TREES [J].
COCKAYNE, EJ ;
HEDETNIEMI, ST ;
SLATER, PJ .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 26 (01) :78-80
[8]   Linear hypergraphs with large transversal number and maximum degree two [J].
Dorfling, Michael ;
Henning, Michael A. .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 :231-236
[9]   INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].
ERDOS, P ;
RADO, R ;
KO, C .
QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&
[10]   INDEPENDENCE, CLIQUE SIZE AND MAXIMUM DEGREE [J].
FAJTLOWICZ, S .
COMBINATORICA, 1984, 4 (01) :35-38