Decomposition of bipartite graphs under degree constraints

Broersma, H.J. and Faudree, R.J. and Heuvel van den, J. and Veldman, H.J. (1993) Decomposition of bipartite graphs under degree constraints. Networks, 23 (3). pp. 159-164. ISSN 0028-3045

Preview

PDF
324Kb

Abstract:	Let G = (A, B; E) be a bipartite graph. Let e1, e2 be nonnegative integers, and f1, f2 nonnegative integer-valued functions on V(G) such that ei ≤\|E\|≤ e1 + e2 and fi(v)≤d(v)≤f1(v) + f2(v) for all v ε V(G) (i = 1, 2). Necessary and sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G1 = (A, B; E1) and G2 = (A, B; E2) such that \|Ei\|≤ei and dGi(v)≤fi(v) for all v ε V(G) (i = 1, 2). The result generalizes a known characterization of bipartite graphs with a k-factor. Its proof uses flow theory and is a refinement of the proof of an analogous result due to Folkman and Fulkerson. By applying corresponding flow algorithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved.
Item Type:	Article
Copyright:	© 1993 Wiley InterScience
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/71001
Official URL:	http://dx.doi.org/10.1002/net.3230230303
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page

Metis ID: 140380