Broadcasting in cycle prefix digraphs (Q1392525)

The cycle prefix digraph \(\Gamma_\Delta (D)\), \(\Delta\geq D\), has each vertex labelled with a sequence of distinct symbols \(x_1x_2 \dots x_D\) from an alphabet of \(\Delta+1\) symbols. Directed adjacencies are defined by: \[ \begin{aligned} x_1x_2 \dots x_D\to x_2x_3 \dots x_Dx_{D+1} \quad &\text{for } x_{D+1}\neq x_1,x_2, \dots, x_D \\ x_1x_2 \dots x_D \to x_1x_2 \dots x_{k-1} x_{k+1} \dots x_Dx_k \quad & \text{for } 1\leq k\leq D-1. \end{aligned} \] The broadcast time \(b(\Gamma_\Delta (D))\) is shown to satisfy \(b(\Gamma_\Delta (D))\leq \Delta+ \tfrac 12 D(D-1)\), which is better than for comparable de Bruijn digraphs. Some comparisons are also made with Kautz digraphs.