Skip to Main content Skip to Navigation
Journal articles

Edge Disjoint Hamilton Cycles in Knödel Graphs

Abstract : The 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01352842
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 17, 2016 - 10:53:06 AM
Last modification on : Thursday, September 7, 2017 - 1:03:45 AM
Long-term archiving on: : Friday, November 18, 2016 - 10:09:21 AM

File

2689-9971-1-PB.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-01352842, version 1

Collections

Citation

Palanivel Subramania Nadar Paulraja, S Sampath Kumar. Edge Disjoint Hamilton Cycles in Knödel Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.263-284. ⟨hal-01352842⟩

Share

Metrics

Record views

94

Files downloads

841