Matchings in bipartite graphs with a given number of cuts.

A matching in a graph is a set of pairwise nonadjacent edges. Denote by m (G , k) the number of matchings of cardinality k in a graph G. A quasi-order ⪯ is defined by G ⪯ H whenever m (G , k) ≤ m (H , k) holds for all k. Let BG 1 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut vertices, and BG 2 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut edges. We determine the greatest and least elements with respect to this quasi-order in BG 1 (n , γ) and the greatest element in BG 2 (n , γ) for all values of n and γ. As corollaries, we find that these graphs maximize (resp. minimize) the Hosoya index and the matching energy within the respective sets. [ABSTRACT FROM AUTHOR]