In this note we investigate a special form of degree games de ned by D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó . Usually the board of a graph game is the edge set of Kn, the complete graph on n vertices. Maker and Breaker alter-nately 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 Kn, Maker rst selects as few edges of Kn as possible in order to win, and our goal is to compute the necessary size of that board. Solving a question of , we show, using the discharging method, that the sharp bound is around 10n=7 for the positive minimum degree game.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics