The Forwarding Indices of Graphs -- a Survey <s> Optimal Graphs <s> For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge-forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP-complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge-forwarding index. © 1994 John Wiley & Sons, Inc. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Optimal Graphs <s> Due to recent developments of parallel and distributed computing, the design and analysis of various interconnection networks has been a main topic of research for the past few years and is still stimulated by the new technologies of communication networks such as optic fibers. There are many advantages in using Cayley (di)graphs as models for interconnection networks. This work first surveys some classes of Cayley graphs which are well studied as models of interconnection networks. Results and problems related to routings in networks are then presented, with emphasis on loads of nodes and links in routings. <s> BIB002
A graph G is said to be vertex-optimal if π(G) = A(G), and edge-optimal if Heydemann et al  showed that the equality (3) is valid for any Cayley graph. Theorem 2.8 Let G be a connected Cayley graph with order n. Then From Theorem 2.8, Cayley graphs are vertex-optimal. Some results and problems on the forwarding indices of vertex-transitive or Cayley graphs, an excellent survey on this subject has been given by Heydemann BIB002 . Heydemann et al BIB001 have constructed a class of graphs for which the vertexforwarding index is not given by a minimal consistent routing. Thus, they suggested the following problems worthy of being considered. BIB001 ) For which graph or digraph G does there exist a minimal consistent routing R such that