On imbalances in orientired bipartite graphs

Abstract

An oriented bipartite graph is the result of assigning a direction to each edge of a simple bipartite graph. For any vertex x in an oriented bipartite graph D(U,V), let d⁺_x and d^-_x respectively denote the outdegree and indegree of x. Define a_ui = d⁺_ui - d^-_ui and b_vj = d⁺_vj - d^-_vj respectively as the imbalances of vertices u_i in U and v_j in V. In this paper, we obtain constructive and existence criteria for a pair of sequences of integers to be the imbalances of some oriented bipartite graph. We also show the existence of a bipartite oriented graph with given imbalance set.