Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

Edge Disjoint Hamilton Cycles in Knödel Graphs

Paulraja Palanivel Subramania Nadar, Sampath Kumar S

Abstract


The vertices of the Knödel graph WΔ, n on n≥2 vertices, n even, and of maximum degree Δ, 1≤Δ≤⌊log2(n)⌋, are the pairs (i, j) with i =1, 2 and 0≤j≤n / 2-1. For 0≤j≤n / 2-1, there is an edge between vertex (1, j) and every vertex (2, j+2k-1 (mod n / 2)), for k=0, 1, 2,…,Δ-1. Existence of a Hamilton cycle decomposition of Wk, 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 Wk,2k, k≥6 has ⌊k / 2⌋-1 edge disjoint Hamilton cycles.

Full Text: PDF PostScript