The matcher game played in graphs

Wayne Goddard, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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 languageEnglish
Pages (from-to)82-88
Number of pages7
JournalDiscrete Applied Mathematics
Publication statusPublished - 11 Mar 2018


  • Matcher game
  • Matching

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'The matcher game played in graphs'. Together they form a unique fingerprint.

Cite this