A $[k,k+1]$-Factor Containing A Given Hamiltonian Cycle

Cai Mao-cheng, Yanjun Li, Mikio Kano


We prove the following best possible result. Let $k\ge 2$ be an integer and $G$ be a graph of order $n$ with minimum degree at least $k$. Assume $n \ge 8k-16$ for even $n$ and $n \ge 6k-13$ for odd $n$. If the degree sum of each pair of nonadjacent vertices of $G$ is at least $n$, then for any given Hamiltonian cycle $C$ of $G$, $G$ has a $[k,\,k+1]$-factor containing $C$.

Full Text: PDF