Game matching number of graphs.

Abstract: We study a competitive optimization version of , the maximum size of a matching in a graph . Players alternate adding edges of to a matching until it becomes a maximal matching. One player (Max) wants the final matching to be large; the other (Min) wants it to be small. The resulting sizes under optimal play when Max or Min starts are denoted and , respectively. We show that always . We obtain a sufficient condition for . Always , with equality for many split graphs, while when is a forest. Whenever is a -regular -vertex connected graph, , and such graphs exist with . For an -vertex path or cycle, the value is roughly . [Copyright &y& Elsevier]