Edge Disjoint Hamilton Cycles in Knödel Graphs - Palanivel Subramania Nadar Paulraja; S Sampath Kumar (Discrete Mathematics & Theoretical Computer Science, 2016)
The vertices of the Knödel graph $W_{Δ, n}$ on $n ≥ 2$ vertices, $n$ even, and of maximum degree $Δ, 1 ≤ Δ ≤ \lfloor log_2(n) \rfloor$, are the pairs $(i,j)$ with $i=1,2$ and $0 ≤ j ≤ \frac{n}{2} -1$. For $0 ≤ j ≤ \frac{n}{2} -1$, there is an edge between vertex $(1,j)$ and every vertex $(2,j + 2^k - 1 (mod \frac{n}{2}))$, for $k=0,1,2, … , Δ -1$. Existence of a Hamilton cycle decomposition of $W_{k, 2k}, k ≥ 6$ is not yet known, see Discrete Appl. Math. 137 (2004) 173-195. In this paper, it is shown that the $k$-regular Knödel graph $W_{k,2k}, k ≥ 6$ has $ \lfloor \frac{k}{2} \rfloor - 1$ edge disjoint Hamilton cycles.