On imbalances in multipartite multidigraphs

Abstract

A k-partite r-digraph(multipartite multidigraph) (or briefly MMD)(k ≥ 3, r ≥ 1) is the result of assigning a direction to each edge of a k-partite multigraph that is without loops and contains at most r edges between any pair of vertices from distinct parts. Let D(X₁, X₂, ⋯, X_k) be a k-partite r-digraph with parts X_i = {x_i1, x_i2, ⋯, x_ini}, 1 ≤ i ≤ k. Let d_xij⁺ and d_xij⁻ be respectively the outdegree and indegree of a vertex x_ij in X_i. Define a_xij (or simply a_ij) as a_ij = d_xij⁺ − d_xij⁻ as the imbalance of the vertex x_ij, 1 ≤ j ≤ n_i. In this paper, we characterize the imbalances of k-partite r-digraphs and give a constructive and existence criteria for sequences of integers to be the imbalances of some k-partite r-digraph. Also, we show the existence of a k-partite r-digraph with the given imbalance set.