The Forwarding Indices of Graphs -- a Survey <s> Problem 2.9 (Heydemann et al <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> Problem 2.9 (Heydemann et al <s> Abstract We define a graph as orbital regular if there is a subgroup of its automorphism group that acts regularly on the set of edges of the graph as well as on all its orbits of ordered pairs of distinct vertices of the graph. For these graphs there is an explicit formula for the edge-forwarding index, an important traffic parameter for routing in interconnection networks. Using the arithmetic properties of finite fields we construct infinite families of graphs with low edge-forwarding properties. In particular, the edge-forwarding index of Paley graphs is determined. A connection with the Waring problem over finite fields and the coset weight enumeration of certain cyclic codes is established. <s> BIB002 </s> The Forwarding Indices of Graphs -- a Survey <s> Problem 2.9 (Heydemann et al <s> We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs. <s> BIB003 </s> The Forwarding Indices of Graphs -- a Survey <s> Problem 2.9 (Heydemann et al <s> Abstract We introduce the concept of quasi-Cayley graphs, a class of vertex-transitive graphs which contains Cayley graphs, and study some of their properties. By finding vertex-transitive graphs which are not quasi-Cayley graphs we give a negative answer to a question by Fuller and Krishnamurthy on the quasi-group representation of a vertex-transitive graph. <s> BIB004
Heydemann et al BIB001 have ever conjectured that in any vertex-transitive graph G, there exists a minimal routing R m in which the equality (4) holds. The conjecture has attracted many researchers for ten years and more without a complete success until 2002. Shim,Širáň andŽerovnik  disproved this conjecture by constructing an infinite family of counterexamples, that is, K p ⊕ P (10, 2) for any q ≡ 0 (mod 3), where P (10, 2) is the generalized Petersen graph and the symbol ⊕ denotes the strong product. Gauyacq BIB004 BIB003  defined a class of quasi-Cayley graphs, a new class of vertextransitive graphs, which contain Cayley graphs, and are vertex-optimal. Solé BIB002 constructed an infinite family of graphs, the so-called orbital regular graphs, which are edge-optimal. We state the results of Gauyacq and Solé as the following theorem. Theorem 2.10 Any quasi-Cayley graph is vertex-optimal, and any orbital regular graph is edge-optimal. However, we have not yet known whether a quasi-Cayley graph is edge-optimal and not known whether an orbital regular graph is vertex-optimal. Thus, we suggest to investigate the following problem.