Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871470 | Discrete Applied Mathematics | 2018 | 7 Pages |
Abstract
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 αgâ²(G) of a graph G is the number of edges chosen when both players play optimally. In this paper it is proved that αgâ²(G)â¥23αâ²(G), where αâ²(G) denotes the matching number of graph G, and this bound is tight. Further, if G is bipartite, then αgâ²(G)=αâ²(G). We also provide some results on graphs of large odd girth and on dense graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wayne Goddard, Michael A. Henning,