On arc-disjoint Hamiltonian cycles in

Abstract. We give two equivalent formulations of a conjecture [2,4] on the number of arc-disjoint Hamiltonian cycles in De Bruijn graphs. A De Bruijn word of type (q, k) for a given q and k is a word over an alphabet with q letters, containing all k-length words exactly once. The length of such a word is qk + k − 1. For example if q = 3, k = 2, then 0012202110 is a De Bruijn word of type (3, 2). For a q-letter alphabet A the De Bruijn graph B(q, k) is defined as: B(q, k) = (V (q, k), E(q, k)) with • V (q, k) = Ak the set of vertices • E(q, k) = Ak+1 the set of directed arcs • there is an arc from vertex x1x2... xk to vertex y1y2... yk if x2x3... xk = y1y2... yk−1 and this arc is denoted by x1x2... xkyk. In the De Bruijn graph B(q, k) a path (i. e. a walk with distinct vertices