Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427002 | Information Processing Letters | 2016 | 4 Pages |
•We have presented an extension of Hall's theorem in partitioned bipartite graph G.•We have proved a necessary and sufficient condition for the existence of specific matching in G.•We have showed that this matching can be computed in polynomial time.
Let G=(X,Y,E)G=(X,Y,E) be a bipartite graph with bipartition X and Y and edge set E such that X is partitioned into a set of k pairwise disjoint subsets X1,X2,…,XkX1,X2,…,Xk. For any sequence n1,n2,…,nkn1,n2,…,nk of natural numbers with ni≤|Xi|ni≤|Xi| for all i, we prove a necessary and sufficient condition for the existence of a semi-perfect matching in G, a matching that includes, for each i , at least nini edges that are incident to vertices from XiXi. Clearly, this is equivalent to Hall's theorem in the case where ni=|Xi|ni=|Xi| for all i.