Two edge-disjoint hamiltonian cycles in the butterfly graph (Q1334638)

A graph is called a butterfly graph of dimension \(n\) if it is the set of couples \((a; x_{n-1}\ldots x_ 0)\), where \(a\in \{0,\dots,n- 1\}\) and \(x_ i\in \{0,1\}\) for all \(i\in \{0,\dots,n- 1\}\), and \([(a;x_{n- 1}\ldots x_ 0)\), \((a';x_{n-1}'\ldots x_ 0')]\) is an edge of the graph if \(a'\equiv a+1\pmod n\) and if \(x_ i= x_ i'\) for all \(i\neq a'\). The paper shows that the butterfly graph contains two edge-disjoint hamiltonian cycles. It also gives a recursive method for constructing these cycles.