Efficient recognition of equimatchable graphs

In this paper, we give a new characterization of equimatchable graphs that are graphs with all maximal matchings having the same size. This gives an O(n(2)m)-algorithm for deciding whether a general graph of order n and with m edges is equimatchable. An O(n(4.5)) recognition algorithm based on the Gallai-Edmonds Decomposition already follows from Lesk et al. (1984) [8]. Our characterization and algorithm use only some basic knowledge on matchings and can be formulated in a simplier way. Moreover it leads to a better time complexity. (C) 2013 Elsevier B.V. All rights reserved.