All Regular Multigraphs of Even Order and High Degree Are 1-factorable

  • Michael J. Plantholt
  • Shailesh K. Tipnis


Plantholt and Tipnis (1991) proved that for any even integer $r$, a regular multigraph $G$ with even order $n$, multiplicity $\mu(G) \leq r$ and degree high relative to $n$ and $r$ is 1-factorable. Here we extend this result to include the case when $r$ is any odd integer. Häggkvist and Perković and Reed (1997) proved that the One-factorization Conjecture for simple graphs is asymptotically true. Our techniques yield an extension of this asymptotic result on simple graphs to a corresponding asymptotic result on multigraphs.

Article Number