2022/03/23 by Amin Bahmanian, Bahmanian, Amin
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #VLSI and FPGA Design Techniques #cs.DM #graph theory and CDMA systems #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.2203.12470
3 pages
arxiv created 2022/03/23 · arxiv updated 2022/03/24
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)≤ degF(x) ≤ f(x) for x∈ X and degF(y) ≤ f(y) for y∈ Y if and only if ∑\nolimitsb∈ B f(b)≥ ∑\nolimitsa∈ A max \0, g(a) - degG-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)≤ degF(x)≤ f(x)≤ deg(x) for x∈ X, degF(y)≤ m for y∈ Y if and only if ∑y∈ NG(S)f(y)≥ ∑x∈ Sg(x) for S⊆ X.