3
$\begingroup$

I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, something of the form $\delta(G) \geq f(k)$. Any suggestions? 10x!

To clarify a bit what I'm after: there is a theorem by Nishimura that ensures a k-factor for k not larger than n/4 or so. But I want a k-factor with k approaching n.

http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190160205/abstract

$\endgroup$
3
  • $\begingroup$ Note that $\delta(G) \geq f(k)$ will not do since there are graphs of arbitrarily high minimum degree without 1-factors (e.g $K_{2n+1}$). $\endgroup$
    – Tony Huynh
    Apr 4, 2012 at 4:16
  • $\begingroup$ You are right. What's the simplest I can get, then? $\endgroup$ Apr 4, 2012 at 8:34
  • $\begingroup$ Hold on a sec: $K_{2n+1}$ does have a 2-factor, right? So maybe it's still possible? $\endgroup$ Apr 4, 2012 at 8:57

1 Answer 1

3
$\begingroup$

A similar theorem is proved in "Relating minimum degree and the existence of a k-factor" by Hartke, Martin and Seacrest.

They show that a graph $G$ on $n$ vertices with minimum degree $\delta\geq \frac{n}{2}$ contains a $k$-factor if $kn$ is even and $$k< \frac{\delta+\sqrt{2\delta n-n^2+8}}{2}.$$

Moreover they show that this is optimal up to a small additive constant ($\le 1$). Notice that as $\delta\to n$ we have $k\to n$, as well.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.