On a conjecture that strengthens Kundu's $k$-factor Theorem

Abstract

Let $\ddot{I}€=(d_1,\dots ,d_n)$ be a non-increasing degree sequence with even $n$. In 1974, Kundu showed that if ${\mathcal{D}}_k(\ddot{I}€)=(d_1-k,\dots ,d_n-k)$ is graphic, then some realization of $\ddot{I}€$ has a $k$-factor. For $r\le 2$, Busch et al. and later Seacrest for $r\le 4$ showed that if $r\le k$ and ${\mathcal{D}}_k(\ddot{I}€)$ 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\le \min \{\lceil \frac{k+5}{3}\rceil ,k\}$. In 1978, Brualdi and then Busch et al. in 2012, conjectured that $r=k$. The conjecture is still open for $k\ge 6$. However, Busch et al. showed the conjecture is true when $d_1\le \frac{n}{2}+1$ or $d_n\ge \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(\ddot{I}€)$ is graphic and show that if $d_{d_1-d_n+k}\ge d_1-d_n+k-1,$ then $\ddot{I}€$ has a realization with $k$ edge-disjoint $1$-factors. From this we confirm the conjecture when $d_n\ge \frac{d_1+k-1}{2}$ or when ${\mathcal{D}}_k(\ddot{I}€)$ is graphic and $d_1\le \max \{n/2+d_n-k,(n+d_n)/2\}$.

27 pages, 2 figures