On the Number of Disjoint Hamiltonian Cycles in De Bruijn Graphs
Bella Bose, Robert Rowley · 1993
We give a constructive proof that there are d-1 disjoint Hamiltonian cycles in the d-ary De Bruijn graph when d is a power of 2. We also demonstrate the existence of at least 2-k pi (p_i*e_i-1), 1>=i>=k, disjoint Hamiltonian cycles where p_1*e_1 * p_2*e_2 ... p_k*e_k is the prime factorization of d.