2-Factors of Bipartite Graphs with Asymmetric Minimum Degrees
2-Factors of Bipartite Graphs with Asymmetric Minimum Degrees
复制标题
DOI：
10.1137/080739513
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
A. Czygrinow;Louis DeBiasio;H. Kierstead
中科院分区：
文献类型：
--
作者：
A. Czygrinow;Louis DeBiasio;H. Kierstead
让$G$和$H$在$2n$顶点上用$\Delta(H)\leq2$平衡$U,V$ -图形。设$k$为$H$、$\delta_U:=\min\{\deg_G(u):u\in U\}$和$\delta_V:=\min\{\deg_G(v):v\in V\}$的组件数。我们证明如果$n$足够大且$\delta_U+\delta_V\geq n+k$，则$G$包含$H$。这回答了在$n$很大的情况下Amar的一个问题。我们还表明，即使$\delta_U+\delta_V\geq n+2$只要$n$在$k$和$\delta(G)\geq\frac{n}{200k}+1$方面足够大，$G$也包含$H$。
Let $G$ and $H$ be balanced $U,V$-bigraphs on $2n$ vertices with $\Delta(H)\leq2$. Let $k$ be the number of components of $H$, $\delta_U:=\min\{\deg_G(u):u\in U\}$ and $\delta_V:=\min\{\deg_G(v):v\in V\}$. We prove that if $n$ is sufficiently large and $\delta_U+\delta_V\geq n+k$, then $G$ contains $H$. This answers a question of Amar in the case that $n$ is large. We also show that $G$ contains $H$ even when $\delta_U+\delta_V\geq n+2$ as long as $n$ is sufficiently large in terms of $k$ and $\delta(G)\geq\frac{n}{200k}+1$.