Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem (Q5928874)

The authors study the integral uniform flow problem in a graph \(G\) and construct a fractional solution whose properties are invariant under the action of a group of automorphisms. The fraction solution is shown to be close to an integral solution, and becomes an integral solution for a class of graphs containing the Cayley graphs. As an application, the authors estimate asymptotically the edge congestion of an optimal integral uniform flow in the cube-connected cycles and the butterfly. They also find the best-known lower bound on the crossing number of a butterfly.