Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653195 | European Journal of Combinatorics | 2017 | 17 Pages |
Let H=(V,E)H=(V,E) be a hypergraph with vertex set VV and edge set EE of order nH=|V|nH=|V| and size mH=|E|mH=|E|. A transversal in HH is a subset of vertices in HH that has a nonempty intersection with every edge of HH. A vertex hits an edge if it belongs to that edge. The transversal game played on HH involves of two players, Edge-hitter and Staller , who take turns choosing a vertex from HH. 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 HH. 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)τg(H), of HH 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τg, that we call the Transversal Continuation Principle. It is known that if HH is a hypergraph with all edges of size at least 22, and HH is not a 44-cycle, then τg(H)≤411(nH+mH); and if HH is a (loopless) graph, then τg(H)≤13(nH+mH+1). We prove that if HH is a 33-uniform hypergraph, then τg(H)≤516(nH+mH), and if HH is 44-uniform, then τg(H)≤71252(nH+mH).