Comellas, F.; Mitjana, M. Broadcasting in cycle prefix digraphs. (English) Zbl 0909.05042 Discrete Appl. Math. 83, No. 1-3, 31-39 (1998). 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. Reviewer: E.K.Lloyd (Southampton) Cited in 1 Document MSC: 05C90 Applications of graph theory 05C20 Directed graphs (digraphs), tournaments 68M10 Network design and communication in computer systems 68R10 Graph theory (including graph drawing) in computer science Keywords:cycle prefix digraph; broadcast time; digraphs PDFBibTeX XMLCite \textit{F. Comellas} and \textit{M. Mitjana}, Discrete Appl. Math. 83, No. 1--3, 31--39 (1998; Zbl 0909.05042) Full Text: DOI Link References: [1] Bermond, J. C.; Peyrat, C., Broadcasting in de Bruijn networks, (Congr. Numer., 66 (1988)), 283-292 · Zbl 0673.94027 [2] Berthomé, P.; Ferreira, A.; Perennes, S., Optimal information dissemination in Star and Pancake networks, Tech. Rept. LIP, ENS-Lyon (1992) [3] Chen, W. Y.C.; Faber, V.; Knill, E., Restricted routing and wide diameter of the cycle prefix network, (Tech. Rept. LACES-94C-94-5 (1994), Los Alamos National Laboratory: Los Alamos National Laboratory Los Alamos, NM) · Zbl 0838.68006 [4] Comellas, F.; Fiol, M. A., Vertex symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1-11 (1995) · Zbl 0822.05033 [5] Faber, V.; Moore, J. W., High-degree low-diameter interconnection networks with vertex symmetry: directed case, (Tech. Rept. LA-UR-88-1051 (1988), Los Alamos National Laboratory: Los Alamos National Laboratory Los Alamos, NM) [6] Faber, V.; Moore, J. W.; Chen, W. Y.C., Cycle prefix digraphs for symmetric interconnection networks, Networks, 23, 641-649 (1993) · Zbl 0802.90043 [7] GowriSankaran, C., Broadcasting on recursively decomposable Cayley graphs, Discrete Appl. Math., 53, 171-182 (1994) · Zbl 0807.94032 [8] Hamidoune, Y. O.; Lladó, A. S.; Serra, O., The connectivity of hierarchical Cayley digraphs, Discrete Appl. Math., 37/38, 275-280 (1992) · Zbl 0776.05048 [9] Heydemann, M. C.; Opatrny, J.; Sotteau, D., Broadcasting and spanning trees in de Bruijn and Kautz networks, Discrete Appl. Math., 37/38, 297-317 (1992) · Zbl 0755.94017 [10] Hsu, D. F., On container width and length in graphs, groups and networks, IEICE Trans. Fundamentals, E77-A, 668-680 (1994) [11] Jiang, M.; Ruskey, K., Determining the Hamilton-connectedness of certain vertex transitive graphs, Discrete Math., 133, 159-170 (1994) · Zbl 0824.05044 [12] Knill, E., Notes on the connectivity of Cayley coset digraphs, (Tech. Rept. LAUR-94-3719 05C-94-30 (1994), Los Alamos National Laboratory: Los Alamos National Laboratory Los Alamos, NM) [13] Sabidussi, G., Vertex transitive graphs, Monatsh. Math., 68, 426-438 (1969) · Zbl 0136.44608 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.