TY - JOUR
T1 - Bounds on the game transversal number in hypergraphs
AU - Bujtás, Csilla
AU - Henning, Michael A.
AU - Tuza, Zsolt
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/1/1
Y1 - 2017/1/1
N2 - Let H=(V,E) be a hypergraph with vertex set V and edge set E of order nH=|V| and size mH=|E|. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. A vertex hits an edge if it belongs to that edge. The transversal game played on H involves of two players, Edge-hitter and Staller, who take turns choosing a vertex from H. Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in H. Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The game transversal number, τg(H), of H is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of τg, that we call the Transversal Continuation Principle. It is known that if H is a hypergraph with all edges of size at least 2, and H is not a 4-cycle, then τg(H)≤[formula parsented](nH+mH); and if H is a (loopless) graph, then τg(H)≤[formula parsented](nH+mH+1). We prove that if H is a 3-uniform hypergraph, then τg(H)≤[formula parsented](nH+mH), and if H is 4-uniform, then τg(H)≤[formula parsented](nH+mH).
AB - Let H=(V,E) be a hypergraph with vertex set V and edge set E of order nH=|V| and size mH=|E|. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. A vertex hits an edge if it belongs to that edge. The transversal game played on H involves of two players, Edge-hitter and Staller, who take turns choosing a vertex from H. Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in H. Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The game transversal number, τg(H), of H is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of τg, that we call the Transversal Continuation Principle. It is known that if H is a hypergraph with all edges of size at least 2, and H is not a 4-cycle, then τg(H)≤[formula parsented](nH+mH); and if H is a (loopless) graph, then τg(H)≤[formula parsented](nH+mH+1). We prove that if H is a 3-uniform hypergraph, then τg(H)≤[formula parsented](nH+mH), and if H is 4-uniform, then τg(H)≤[formula parsented](nH+mH).
UR - http://www.scopus.com/inward/record.url?scp=84980347704&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2016.07.003
DO - 10.1016/j.ejc.2016.07.003
M3 - Article
AN - SCOPUS:84980347704
SN - 0195-6698
VL - 59
SP - 34
EP - 50
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -