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, AQ(n), is the Cayley graph (Z(2)(n), {e(1), e(2), . . ., e(n),.J(2), . . ., J(n)) where e(i)'s are the vectors of the standard basis and J(i) = Sigma(n)(j=n-i+1) e(j.)S.A Choudum and V. Sunitha showed that the greedy algorithm provides a shortest path between each pair of vertices of AQ(n). Min Xu and Jun-Ming Xu claimed that this routing also proves that the edge-forwarding index of AQ(n) is 2(n-1). Here we disprove this claim, by showing that in this specific routing some edges are repeated nearly 4/32(n-1) times (to be precise, [2(n+1)/3] for even values of n and [2(n+1)/3] for odd values of n). However, by providing other routings, we prove that 2(n-1) is indeed the edge-forwarding index of AQ(n). (C) 2018 Elsevier B.V. All rights reserved.