## 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)≥[Formula presented]α^{′}(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.

Original language | English |
---|---|

Pages (from-to) | 82-88 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 237 |

DOIs | |

Publication status | Published - 11 Mar 2018 |

## Keywords

- Matcher game
- Matching

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics