Edge-foreward index of star graphs and other Cayley graphs
type: Item
instance of: scholarly article
title: Edge-foreward index of star graphs and other Cayley graphs
zbMATH Open document ID: 0897.05043
DOI: 10.1016/S0166-218X(97)00052-8
author: Ginette Gauyacq
published in: Discrete Applied Mathematics
publication date: 1998-10-05T00:00:00Z
full work available at URL: dam
review text: 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.
reviewed by: Brigitte Servatius
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1133167
zbMATH Keywords: Cayley graphs
zbMATH Keywords: routings
zbMATH Keywords: forwarding index
MaRDI profile type: Publication
cites work: A group-theoretic model for symmetric interconnection networks
cites work: Q5422499
cites work: The forwarding index of communication networks
cites work: The minimum-length generator sequence problem is NP-hard
cites work: Q4232791
cites work: On forwarding indices of networks
cites work: Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
cites work: The edge-forwarding index or orbital regular graphs
description: scientific article; zbMATH DE number 1133167