On Factors with Prescribed Degrees in Bipartite Graphs
share
We establish a new criterion for a bigraph to have a subgraph with prescribed degree conditions. We show that the bigraph G[X,Y] has a spanning subgraph F such that g(x)≤ deg_F(x) ≤ f(x) for x∈ X and deg_F(y) ≤ f(y) for y∈ Y if and only if ∑_b∈ B f(b)≥∑_a∈ Amax{0, g(a) - deg_G-B(a)} for A⊆ X, B⊆ Y. Using Folkman-Fulkerson's Theorem, Cymer and Kano found a different criterion for the existence of such a subgraph (Graphs Combin. 32 (2016), 2315–2322). Our proof is self-contained and relies on alternating path technique. As an application, we prove the following extension of Hall's theorem. A bigraph G[X,Y] in which each edge has multiplcity at least m has a subgraph F with g(x)≤ deg_F(x)≤ f(x)≤ deg(x) for x∈ X, deg_F(y)≤ m for y∈ Y if and only if ∑_y∈ N_G(S)f(y)≥∑_x∈ Sg(x) for S⊆ X.
READ FULL TEXT