Bounds on the game transversal number in hypergraphs. (January 2017)

• Record Type: Journal Article
• Authors: Bujtás, Csilla; Henning, Michael A.; Tuza, Zsolt
• Is Part Of: European journal of combinatorics. Volume 59(2017)
• Page Start: 34
• Page End: 50
• Publication Date: 2017-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.07.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Let H = ( V, E ) be a hypergraph with vertex set V and edge set E of order n H = | V | and size m H = | 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 ) ≤ 4 11 ( n H + m H ) ; and if H is a (loopless) graph, then τ g ( H ) ≤ 1 3 ( n H + m H + 1 ) . We prove that if H is a 3 -uniform hypergraph, then τ g ( H ) ≤ 5 16 ( n H + m H ), and if H is 4 -uniform, then τ g ( H ) ≤ 71 252 ( n H + m H ) .