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 |U|=n, |V|=m, and n>m>1, which is k-critical bipartite, and the tuple (|E|,ΔU,ΔV), where ΔU and Δ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