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