The Forwarding Indices of Graphs -- a Survey <s> Methods of Determining the Forwarding Indices <s> A generalization of the cube-connected cycles of Preparata and Vuillemin is described which retains the symmetry of these architectures while allowing for constructions of greater density and of arbitrary degree. These constructions are of a type known as Cayley graphs, and their analysis is greatly facilitated by the applicability of methods from abstract algebra. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Methods of Determining the Forwarding Indices <s> Abstract We study the integral uniform (multicommodity) flow problem in a graph G and construct a fractional solution whose properties are invariant under the action of a group of automorphisms Γ <s> BIB002 </s> The Forwarding Indices of Graphs -- a Survey <s> Methods of Determining the Forwarding Indices <s> For a given connected graph G of order n, a routing R in G is a set of n(n-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71-84] proposed a variant of the hypercube Q"n, called the augmented cube AQ"n and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of AQ"n as 2^n9+(-1)^n^+^19+n2^n3-2^n+1 and 2^n^-^1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity. <s> BIB003 </s> The Forwarding Indices of Graphs -- a Survey <s> Methods of Determining the Forwarding Indices <s> For a given connected graph $G$ of order $n$, a routing $R$ is a set of $n(n-1)$ elementary paths specified for every ordered pair of vertices in $G$. The vertex-forwarding index $\xi(G)$ (the edge-forwarding index $\pi(G)$) of $G$ is the maximum number of paths of $R$ passing through any vertex (resp. edge) in $G$. In this paper we consider the vertex- and the edge- forwarding indices of the cartesian product of $k\,(\ge 2)$ graphs. As applications of our results, we determine the vertex- and the edge- forwarding indices of some well-known graphs, such as the $n$-dimensional generalized hypercube, the undirected toroidal graph, the directed toroidal graph and the cartesian product of the Petersen graphs. <s> BIB004 </s> The Forwarding Indices of Graphs -- a Survey <s> Methods of Determining the Forwarding Indices <s> For a given connected graph G of order v, a routing R in G is a set of v(v-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Shahrokhi and Szekely [F. Shahrokhi, L.A. Szekely, Constructing integral flows in symmetric networks with application to edge forwarding index problem, Discrete Applied Mathematics 108 (2001) 175-191] obtained an asymptotic formula for the edge forwarding index of n-dimensional cube-connected cycle CCC"n as 54n^22^n(1-o(1)). This paper determines the vertex forwarding index of CCC"n as 74n^22^n(1-o(1)) asymptotically. <s> BIB005
To the knowledge of the author, one of the actual methods of determining forwarding index is to compute the sum of all pairs of vertices according to (4) for some Cayley graphs. In fact, the forwarding indices of many Cayley graphs are determined by using (4), for example, the folded cube  , the augmented cube BIB003 and so on, list in the next section. Although Cayley graphs, one class of vertex-transitive graphs, are of hight symmetry, it is not always easy to compute the distance from a fixed vertex to all other vertices for some Cayley graphs. For example, The n-dimensional cube-connected cycle CCC n , constructed from Q n by replacing each of its vertices with a cycle C n = (0, 1, . . . , n − 1) of length n, is a Cayley graph proved by Carlsson et al. BIB001 . Until now, one has not yet determined exactly its sum of all pairs of vertices, and so only can give its forwarding indices asymptotically (see, Shahrokhi and Székely BIB002 , and Yan et al. BIB005 ). Unfortunately, for the edge-forwarding index, there is no an analogy of (4). But the lower bound of π(G) given in (2) is useful. One may design a routing R such that π(G, R) attains this lower bound. For example, the edge-forwarding indices of the folded cube  and the augmented cube BIB003 are determined by this method. Making use of results on the Cartesian product is one of methods determining forwarding indices. Using Theorem 2.15, Xu et al BIB004 determined the vertex-forwarding indices and the edge-forwarding indices for the generalized hypercube , all of which can be regarded as the Cartesian products.