Skip to main content

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.

U.S. flag

An official website of the United States government

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}.
Citation
Journal of Graph Theory
Volume
108
Issue
3

Keywords

degree sequence, k-factor, regular graph, perfect matching

Citation

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)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created October 6, 2024, Updated March 20, 2025
Was this page helpful?