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

Published

October 6, 2024

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

Pub Type

Journals

Download Paper

https://doi.org/10.1002/jgt.23177

Local Download

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 April 3, 2025)