Bounds on the game transversal number in hypergraphs. (January 2017)
- Record Type:
- Journal Article
- Title:
- Bounds on the game transversal number in hypergraphs. (January 2017)
- Main Title:
- Bounds on the game transversal number in hypergraphs
- Authors:
- Bujtás, Csilla
Henning, Michael A.
Tuza, Zsolt - 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 ) .
- Is Part Of:
- European journal of combinatorics. Volume 59(2017)
- Journal:
- European journal of combinatorics
- Issue:
- Volume 59(2017)
- Issue Display:
- Volume 59, Issue 2017 (2017)
- Year:
- 2017
- Volume:
- 59
- Issue:
- 2017
- Issue Sort Value:
- 2017-0059-2017-0000
- 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 - Journal URLs:
- http://www.sciencedirect.com/science/journal/01956698 ↗
http://www.elsevier.com/journals ↗
http://www.idealibrary.com ↗
http://firstsearch.oclc.org ↗
http://firstsearch.oclc.org/journal=0195-6698;screen=info;ECOIP ↗ - DOI:
- 10.1016/j.ejc.2016.07.003 ↗
- Languages:
- English
- ISSNs:
- 0195-6698
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3829.728200
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 634.xml