On imbalances in multipartite multidigraphs

Uma Tul Samee, Shariefuddin Pirzada


A $k$-partite $r$-digraph(multipartite multidigraph) (or briefly MMD)($k\geq 3$, $r\geq 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_{1}, X_{2},\cdots, X_{k})$ be a $k$-partite $r$-digraph with parts $X_{i}=\{x_{i1}, x_{i2},\cdots, x_{in_{i}}\}$, $1\leq i\leq k$. Let $d_{x_{ij}}^{+}$ and $d_{x_{ij}}^{-}$ be respectively the outdegree and indegree of a vertex $x_{ij}$ in $X_{i}$. Define $a_{x_{ij}}$ (or simply $a_{ij}$) as $a_{ij}=d_{x_{ij}}^{+}-d_{x_{ij}}^{-}$ as the imbalance of the vertex $x_{ij}$, $1\leq j\leq 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.


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