论文标题
在增强昆杜的$ k $ -factor定理的猜想中
On a conjecture that strengthens Kundu's $k$-factor Theorem
论文作者
论文摘要
令$π=（d_ {1}，\ ldots，d_ {n}）$是具有甚至$ n $的非缩写度序列。 1974年，Kundu表明，如果$ \ Mathcal {d} _ {k}（π）=（d_ {1} -k，\ ldots，d_ {n} -k）$是图形的，那么$π$的一些实现具有$ k $ -ftactor。对于$ r \ leq 2 $，Busch等人。后来以$ r \ leq 4 $的价格显示，如果$ r \ leq k $和$ \ mathcal {d} _ {k}（π）$是图形的，那么就可以将$ k $ - factor的边缘划分为$ k $ factor的实现，可以将其划分为$（k-ros）$（k-ros）和$ r $ en $ $ $ $ $ $ 1 $ 1 $ 1 $ 1 $ 1- factors。我们将其改进到任何$ r \ leq \ min \ {\ lceil \ frac {k+5} {3} {3} \ big \ rceil，k \} $。 1978年，Brualdi和Busch等人。 2012年，猜想$ r = k $。猜想仍然以$ k \ geq6 $开放。但是，Busch等。当$ d_ {1} \ leq \ frac {n} {2}+1 $或$ d_ {n} \ geq \ geq \ frac {n} {2} {2}+k-2 $时，显示猜想是正确的。我们通过首先开发概括边缘交换的新工具来探索这种猜想。使用这些新工具，我们可以放弃假设$ \ MATHCAL {d} _ {k}（π）$是图形的，并表明如果$ d_ {d_ {d_ {1} -d_ {n}+k} \ geq d_} \ geq d_ {1} {1} -d_ {n}+k-1，$ k-1，$ $ $ $ $ $ k $ k $ k $ k $ k $ k $ k.从此，我们确认$ d_ {n} \ geq \ frac {d_ {1}+k-1} {2} $或$ \ mathcal {d} _ {k} _ {k}（π）$是图形和$ d_ {1} {1} \ leq \ max \ max \ max \ max \ max \ max \ max \ max， \ {n/2+d_ {n} -k，（n+d_ {n}）/2 \} $。
Let $π=(d_{1},\ldots,d_{n})$ be a non-increasing degree sequence with even $n$. In 1974, Kundu showed that if $\mathcal{D}_{k}(π)=(d_{1}-k,\ldots,d_{n}-k)$ is graphic, then some realization of $π$ has a $k$-factor. For $r\leq 2$, Busch et al. and later Seacrest for $r\leq 4$ showed that if $r\leq k$ and $\mathcal{D}_{k}(π)$ is graphic, then there is a realization with a $k$-factor whose edges can be partitioned into a $(k-r)$-factor and $r$ edge-disjoint $1$-factors. We improve this to any $r\leq \min\{\lceil\frac{k+5}{3}\big\rceil,k\}$. In 1978, Brualdi and then Busch et al. in 2012, conjectured that $r=k$. The conjecture is still open for $k\geq6$. However, Busch et al. showed the conjecture is true when $d_{1}\leq \frac{n}{2}+1$ or $d_{n}\geq \frac{n}{2}+k-2$. We explore this conjecture by first developing new tools that generalize edge-exchanges. With these new tools, we can drop the assumption $\mathcal{D}_{k}(π)$ is graphic and show that if $d_{d_{1}-d_{n}+k}\geq d_{1}-d_{n}+k-1,$ then $π$ has a realization with $k$ edge-disjoint $1$-factors. From this we confirm the conjecture when $d_{n}\geq \frac{d_{1}+k-1}{2}$ or when $\mathcal{D}_{k}(π)$ is graphic and $d_{1}\leq \max \{n/2+d_{n}-k,(n+d_{n})/2\}$.
