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

Improve this question
$\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
    Commented Apr 4, 2012 at 4:16
  • $\begingroup$ You are right. What's the simplest I can get, then? $\endgroup$
    – Felix Goldberg
    Commented 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$
    – Felix Goldberg
    Commented Apr 4, 2012 at 8:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .