Optimally Balanced Orientation of Graphs
Joseph R. Barr, Peter Martin Shaw, Faisal N. Abu-Khzam · 2020
Every graph has orientation δ with the property that the indegree and outdegree of each vertex differ by no more than a unity. For a subset A of vertices of a digraph D the indegree of A is the number of arcs pointing into A and the outdegree of A is the number of arcs pointing out of A. The flux at A is the difference of the two (`in' minus `out'.) For a fixed graph G consider the set Δ of all orientations of G. We calculate “worst-case” flux as the “min-max” flux: the maximum flux over all subsets of vertices and the minimum over all orientations. The min-max flux over A with respect to orientation δ is the “flux” of the graph φδ(A) whereδ∈δminA⊂Vmaxφ(A; δ). An orientation δ of G achieving the min-max is said to be optimally-balanced. In this paper we characterize optimally-balanced graphs.