The optimal routing of augmented cubes

A routing in a graph G is a set of paths connecting each ordered pair of vertices. Load of an edge e is the number of times it appears on these paths. The edge-forwarding index of G is the smallest of maximum loads over all routings. Augmented cube of dimension n, AQn, is the Cayley graph (Z2n,{e1,e2,…,en,J2,…,Jn}) where ei's are the vectors of the standard basis and Ji=∑j=n−i+1nej. S.A. Choudum and V. Sunitha showed that the greedy algorithm provides a shortest path between each pair of vertices of AQn. Min Xu and Jun-Ming Xu claimed that this routing also proves that the edge-forwarding index of AQn is 2n−1. Here we disprove this claim, by showing that in this specific routing some edges are repeated nearly 432n−1 times (to be precise, ⌊2n+13⌋ for even values of n and ⌈2n+13⌉ for odd values of n). However, by providing other routings, we prove that 2n−1 is indeed the edge-forwarding index of AQn.