Skip to main content
added 25 characters in body
Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

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.

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 $\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. Notice that as $\delta\to n$ we have $k\to n$, as well.

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.

Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

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 $\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. Notice that as $\delta\to n$ we have $k\to n$, as well.