Edge-foreward index of star graphs and other Cayley graphs (Q1382271): Difference between revisions

While it is known that in any Cayley graph there exists a vertex-uniform routing of shortest paths, see \textit{F. R. K. Chung, E. G. Coffman, M. I. Reiman}, and \textit{B. Simon} [IEEE Trans. Inf. Theory IT-33, 224--232 (1987; Zbl 0626.94019)], and such a routing yields the minimum (vertex) forwarding index, there are Cayley graphs for which no edge-uniform routing of shortest paths exists, see \textit{M. C. Heydemann, J. C. Meyer, D. Sotteau}, and \textit{J. Opatrny} [Networks 24, No. 1, 75--82 (1994; Zbl 0804.90041)]. By constructing minimal length generating sequences which give rise to vertex-uniform routings, the edge-forwarding index is computed for star graphs [cf. \textit{S. B. Akers} and \textit{B. Krishnamurthy}, IEEE Trans. Comput. 38, No. 4, 555--566 (1989; Zbl 0678.94026)] and complete-transposition graphs.