论文标题
关于两分图中规定学位的因素
On Factors with Prescribed Degrees in Bipartite Graphs
论文作者
论文摘要
我们为Bigraph建立了一个新的标准，可以具有规定学位条件的子图。我们表明，bigraph $ g [x，y] $具有一个跨度的子图$ f $，使得$ g（x）\ leq deg_f（x）\ leq f（x）\ f（x）$ for $ x \ in x $ in x $和$ deg_f（y）\ deg_f（y）\ leq f（y） \ sum \ nolimits_ {a \ in} \ max \ big \ {0，g（a） - deg_ {g -b}（a）\ big \} $ for $ a \ subseteq x，b \ subseteq y $。 Cymer和Kano使用Folkman-Fulkerson的定理发现了这种子图的存在的不同标准（GraphsCombin。32（2016），2315--2322）。我们的证明是独立的，依赖于交替的路径技术。作为应用程序，我们证明了Hall定理的以下扩展。一个bigraph $ g [x，y] $，其中每个边缘的倍数至少具有$ m $具有$ g（x）\ leq deg_f（x）\ leq f（x）\ leq f（x）\ leq f（x）\ leq f（x）\ for $ x $ in x $，$ deg_f（y deg_f（y）for y y y y y y y y y y y y y y y y y y y， n_g（s）} f（y）\ geq \ sum_ {x \ in s} g（x）$ for $ s \ subseteq x $。
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)\leq deg_F(x) \leq f(x)$ for $x\in X$ and $deg_F(y) \leq f(y)$ for $y\in Y$ if and only if $\sum\nolimits_{b\in B} f(b)\geq \sum\nolimits_{a\in A} \max \big\{0, g(a) - deg_{G-B}(a)\big\}$ for $A\subseteq X, B\subseteq 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)\leq deg_F(x)\leq f(x)\leq deg(x)$ for $x\in X$, $deg_F(y)\leq m$ for $y\in Y$ if and only if $\sum_{y\in N_G(S)}f(y)\geq \sum_{x\in S}g(x)$ for $S\subseteq X$.
