The forwarding indices of augmented cubes

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 Qn, called the augmented cube AQn and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of AQn as and 2n−1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity.