Compatible Hamilton decompositions of directed wrapped butterfly graphs (Q1283804)

The directed wrapped butterfly graph of degree \(d\) and dimension \(n\) has vertices \((x,t)\) where \(x = x_{n-1}x_{n-2}\dots x_0 \) is a word of length \(n\) with letters \(x_i\) from the alphabet \(\{0,1,2,\dots ,d-1\}\), and \(0 \leq t \leq n-1\). Vertices are grouped by their level \(t\) and all arcs in the graph go from vertices in level \(t\) to vertices in level \(t+1\) (addition modulo \(n\)) as follows: vertex \(( x_{n-1}x_{n-2}\dots x_n, t)\) is joined by an arc to the \(d\) vertices \(( x_{n-1}x_{n-2}\dots x_{t-1}ax_{t+1}\dots x_n, t+1)\) where \(a \in \{0,1,\dots ,d-1\}\). Vertices in level \(n-1\) are joined to vertices in level \(0\). The author shows that when \(d\) is prime and at least 5, such graphs have a Hamilton decomposition, thus answering a conjecture of \textit{J.-S. Bermond, E. Darrot, O. Delmas} and \textit{S. Perennes} [Discrete Appl. Math. 84, No. 1-3, 21-42 (1998; Zbl 0901.05062)] and completing the Hamiltonian decomposition question for all \(d\) and \(n\). The results are extended to the construction of pairwise compatible sets of Hamilton cycle decompositions (two Hamiton cycle decompositions are compatible if no directed 2-path is in more than one cycle) in the butterfly graph.