Circular Flows of Random Regular Graphs With Large Valency

ABSTRACT

For positive integers with , a circular ‐flow of a graph is defined as a pair where represents an orientation of , and is a function mapping the edges of to the set such that, at each vertex, the sum of the ‐values of the incoming edges equals the sum of the ‐values of the outgoing edges. The flow index of , denoted by , is the infimum among all such that admits a circular ‐flow. Since computing the flow index of a graph is an NP‐hard problem, researchers are wondering whether we can determine the exact values (or the interval) of the flow index of random regular graphs with high probability. Alon and Prałat showed that for large enough , a random ‐regular graph a.a.s. has . In this paper, applying tools from maxcuts and Tutte orientations, we refine the result of Alon and Prałat by proving that for large enough integer , a random ‐regular graph a.a.s. satisfies , where is an explicit constant. That is, an interval of length contains the flow index of random ‐regular graphs with high probability, and thus we asymptotically determine the flow index of almost all ‐regular graphs for sufficiently large .