Find in Library

Let S = (a1,. . . , am; b1, . . . , bn), where a1, . . . , am and b1, . . . , bn are two sequences of nonnegative integers. We say that S is a bigraphic pair if there exists a simple bipartite graph G with partite sets {x1, x2, . . . , xm} and {y1, y2, . . . , yn} such that dG(xi) = ai for 1 ≤ i ≤ m and dG(yj) = bj for 1 ≤ j ≤ n. In this case, we say that G is a realization of S. Analogous to Kundu’s k-factor theorem, we show that if (a1, a2, . . . , am; b1, b2, . . . , bn) and (a1 − e1, a2 − e2, . . . , am − em; b1 − f1, b2 − f2, . . . , bn − fn) are two bigraphic pairs satisfying k ≤ fi ≤ k + 1, 1 ≤ i ≤ n (or k ≤ ei ≤ k + 1, 1 ≤ i ≤ m), for some 0 ≤ k ≤ m − 1 (or 0 ≤ k ≤ n − 1), then (a1, a2, . . . , am; b1, b2, . . . , bn) has a realization containing an (e1, e2, . . . , em; f1, f2, . . . , fn)-factor. For m = n, we also give a necessary and sufficient condition for an (kn; kn)-factorable bigraphic pair to be connected (kn; kn)-factorable when k ≥ 2. This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.