https://hal.inria.fr/hal-01352842Paulraja, Palanivel Subramania NadarPalanivel Subramania NadarPaulrajaDepartment of Mathematics, Kalasalingam University - Kalasalingam UniversitySampath Kumar, SSSampath KumarDepartment of Mathematics, SSN College of Engineering - SSN College of Engineering - Sri Sivasubramaniya Nadar College of EngineeringEdge Disjoint Hamilton Cycles in Knödel GraphsHAL CCSD2016Knödel Graphs Hamilton Cycle Decomposition Tensor Product Bieulerian Graph[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Episciences Iam, Coordination2016-08-17 10:53:062017-09-07 01:03:452016-08-17 11:56:32enJournal articleshttps://hal.inria.fr/hal-01352842/document10.46298/dmtcs.2148application/pdf1The vertices of the Knödel graph $W_{\Delta, n}$ on $n \geq 2$ vertices, $n$ even, and of maximum degree $\Delta, 1 \leq \Delta \leq \lfloor log_2(n) \rfloor$, are the pairs $(i,j)$ with $i=1,2$ and $0 \leq j \leq \frac{n}{2} -1$. For $0 \leq j \leq \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, \ldots , \Delta -1$. Existence of a Hamilton cycle decomposition of $W_{k, 2k}, k \geq 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 \geq 6$ has $\lfloor \frac{k}{2} \rfloor - 1$ edge disjoint Hamilton cycles.