Abstract

We study the problem of Minimum k-Critical Bipartite Graph of order (n, m) - MkCBG-(n, m): to find a bipartite G = (U, V; E), with vertical bar U vertical bar = n, vertical bar V vertical bar = m, and n > m > 1, which is k-critical bipartite, and the tuple (vertical bar E vertical bar, Delta(U), Delta(V)), where Delta(U) and Delta(V) denote the maximum degree in U and V, respectively, is lexicographically minimum over all such graphs. G is k-critical bipartite if deleting at most k = n - m vertices from U creates G' that has a complete matching, i.e., a matching of size m. We show that, if m(n - m + 1)/n is an integer, then a solution of the MkCBG-(n, m) problem can be found efficiently among (a, b)-regular bipartite graphs of order (n, m), with a = m(n - m + 1)/n, and b = n - m + 1. If a = m - 1, then all (a, b)-regular bipartite graphs of order (n, m) are k-critical bipartite. For a m - 1, it is not the case. We characterize the values of n, m, a, and b that admit an (a, b)-regular bipartite graph of order (n, m), with b = n - m + 1, and give a simple construction that creates such a k-critical bipartite graph whenever possible. Our techniques are based on Hall's marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them. (C) 2021 Elsevier B.V. All rights reserved.