On imbalances in multipartite multidigraphs

Uma Tul Samee, Shariefuddin Pirzada


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(X1, X2, ⋯, Xk) be a k-partite r-digraph with parts Xi = {xi1, xi2, ⋯, xini}, 1 ≤ i ≤ k. Let dxij +  and dxij −  be respectively the outdegree and indegree of a vertex xij in Xi. Define axij (or simply aij) as aij = dxij +  − dxij −  as the imbalance of the vertex xij, 1 ≤ j ≤ ni. 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.


digraph, outdegree, imbalance, maximum degree, oriented graph, multipartite multidigraph

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2018.6.1.6


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats