The matcher game played in graphs

摘要

We study a game played on a graph by two players, named Maximizer and Minimizer. Each round two new vertices are chosen; first Maximizer chooses a vertex u that has at least one unchosen neighbor and then Minimizer chooses a neighbor of u. This process eventually produces a maximal matching of the graph. Maximizer tries to maximize the number of edges chosen, while Minimizer tries to minimize it. The matcher number alpha'(g)(G) of a graph G is the number of edges chosen when both players play optimally. In this paper it is proved that alpha'(g)(G) = 2/3 alpha'(G), where alpha'(G) denotes the matching number of graph G, and this bound is tight. Further, if G is bipartite, then alpha'(g)(G) = alpha'(G). We also provide some results on graphs of large odd girth and on dense graphs. (C) 2017 Elsevier B.V. All rights reserved.