Edge-forwarding index of star graphs and other Cayley graphs

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.     

Forwarding index of cube-connected cycles

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 Székely [F. Shahrokhi, L.A. Székely, 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 . This paper determines the vertex forwarding index of CCC_n as asymptotically.