NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
On a conjecture that strengthens Kundu's k-factor Theorem
Published
Author(s)
James Shook
Abstract
Let π = (d1, . . . , dn) be a non-increasing degree sequence with even n. In 1974, Kundu showed that if Dk(π) = (d1 − k, . . . , dn − k) is graphic, then some realization of π has a k-factor. For r ≤ 2, Busch et al. and later Seacrest for r ≤ 4 showed that if r ≤ k and Dk(π) 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 ≤ min⌈k+5 3 ], k}. In 1978, Brualdi and then Busch et al. in 2012, conjectured that r = k. The conjecture is still open for k ≥ 6. However, Busch et al. showed the conjecture is true when d1 ≤ n 2 + 1 or dn ≥ 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 Dk(π) is graphic and show that if dd1−dn+k ≥ d1−dn+k−1, then π has a realization with k edge-disjoint 1-factors. From this we confirm the conjecture when dn ≥ d1+k−1 2 or when Dk(π) is graphic and d1 ≤ maxn/2 + dn − k, (n + dn)/2}.
Shook, J.
(2024),
On a conjecture that strengthens Kundu's k-factor Theorem, Journal of Graph Theory, [online], https://doi.org/10.1002/jgt.23177, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=933481
(Accessed October 9, 2025)