The positive minimum degree game on sparse graphs (Q426781)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The positive minimum degree game on sparse graphs |
scientific article |
Statements
The positive minimum degree game on sparse graphs (English)
0 references
12 June 2012
0 references
Summary: In this note we investigate a special form of degree games defined by \textit{D. Hefetz}, \textit{M. Krivelevich}, \textit{M. Stojaković} and \textit{T. Szabó} [Eur. J. Comb. 32, No. 2, 162--177 (2011; Zbl 1203.91037)]. Usually the board of a graph game is the edge set of \(K_n\), the complete graph on \(n\) vertices. Maker and Breaker alternately claim an edge, and Maker wins if his edges form a subgraph with prescribed properties; here a certain minimum degree. In the special form the board is no longer the whole edge set of \(K_n\), Maker first selects as few edges of \(K_n\) as possible in order to win, and our goal is to compute the necessary size of that board. Solving a question of \textit{D. Hefetz} et al. [loc. cit.], we show, using the discharging method, that the sharp bound is around \(10n/7\) for the positive minimum degree game.
0 references
discharging method
0 references