The Forwarding Indices of Graphs -- a Survey <s> Forwarding Indices of Some Graphs <s> An n-dimensional crossed cube, CQ/sub n/, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n/sup 2/) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2/sup n-1/. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Forwarding Indices of Some Graphs <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> BIB002
The forwarding indices of some very particular graphs have been determined. We list all main results that we are interested in and have known, all of which not noted can be found in Heydemann et at  or determined easily. 1. For a complete graph K n , ξ(K n ) = 0 and π(K n ) = 2. 2. For a star K 1, n−1 , ξ(K 1, n−1 ) = (n − 1)(n − 2) and π(K 1, n−1 ) = 2(n − 1). 3. For a path P n , ξ(P n ) = 2  In particular, 4, for n = 2; 5, for n = 3, 4; 6, for n ≥ 5; 6. The n-dimensional undirected toroidal mesh In particular, The last result was obtained by Heydemann et al  . In particular, 8. The n-dimensional generalized hypercube, denoted by Q(d 1 , d 2 , · · · , d n ), where d i ≥ 2 is an integer for each i = 1, 2, · · · , n, is defined as the cartesian products ) is called the d-ary n-dimensional cube, denoted by Q n (d). It is clear that Q n (2) is Q n . Xu et al BIB002 determined that For the n-dimensional hypercube Q n , ξ(Q n ) = (n − 2)2 n−1 + 1 and π(Q n ) = 2 n . The last result was obtained by Heydemann et al  . 9. For the crossed cube CQ n (n ≥ 2), π(CQ n ) = π m (CQ n ) = 2 n decided by Chang et al BIB001 . However, ξ(CQ n ) has not been determined so far.