Electronic Journal of Graph Theory and Applications

Uma Tul Samee^a, Shariefuddin Pirzada^b

^aDepartment of Mathematics, Islamia College for Science and Commerce, Srinagar, Kashmir, India ^bDepartment of Mathematics, University of Kashmir, Srinagar, Kashmir, India

pzsamee@yahoo.co.in, pirzadasd@kashmiruniversity.ac.in

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.

Keywords: digraph, outdegree, imbalance, maximum degree, oriented graph, multipartite multidigraph Mathematics Subject Classification: 05C20

DOI: 10.5614/ejgta.2018.6.1.6

1. Introduction

A digraph without loops and without multi-arcs is called a simple digraph. The imbalance of a vertex \(v_i\) in a digraph as \(a_{v_i}\) (or simply \(a_i\))= \(d_{v_i}^+ - d_{v_i}^-\), where \(d_{v_i}^+\) and \(d_{v_i}^-\) are respectively the outdegree and indegree of \(v_i\). The imbalance sequence of a simple digraph is formed by listing the vertex imbalances in non-increasing order. For undefined terms, we refer to [12].

Received: 7 October 2017, Revised: 13 January 2018, Accepted: 30 January 2018.

The following result [5] provides a necessary and sufficient condition for a sequence of integers to be the imbalance sequence of a simple digraph.

Theorem 1. A sequence of integers A = [a1, a2, · · · , an] with a¹ ≥ a² ≥ · · · ≥ aⁿ is an imbalance sequence if and only if it has sum zero and satisfies

\[\sum_{i=1}^{k} a_i \le k(n-k),\]

for 1 ≤ k < n, with equality when k = n.

On arranging the imbalance sequence in non-decreasing order, we have the following observation.

Corollary 2. A sequence of integers A = [a1, a2, · · · , an] with a¹ ≤ a² ≤ · · · ≤ aⁿ is an imbalance sequence of a simple digraph if and only if for 1 ≤ k < n

\[\sum_{i=1}^{k} a_i \ge k(k-n),\]

with equality when k = n.

Various results for imbalances in simple digraphs, bipartite and multipartite digraphs can be seen in [6, 8, 9, 27] while as characterization of imbalances in multidigraphs, bipartite multitournaments and tripartite multidigraphs can be found in [7, 10, 11].

An r-digraph (r ≥ 1) is an orientation of a multigraph that is without loops and contains at most r edges between any pair of distinct vertices. Clearly 1-digraph is an oriented graph and complete 1-digraph is a tournament. Various results on scores and marks on tournaments and digraphs can be seen in [2, 13, 14, 15, 16, 17, 18, 24, 25] and on scores and degrees in hypertournaments can be found in [1, 3, 4, 19, 20, 21, 22, 23, 26]. The definition of an imbalance of a vertex in r-digraph is same as in a simple digraph. The following characterization for imbalances in multidigraphs can be found in Pirzada et al. [7].

Theorem 3. A sequence A = [a1, a2, · · · , ap] of integers in non-decreasing order is the imbalance sequence of an r-digraph if and only if

\[\sum_{i=1}^{k} a_i \ge rk(k-n),\]

for 1 ≤ k ≤ n with equality when k = n.

2. Imbalance sequences in multipartite multidigraphs

A k-partite r-digraph (\(k \geq 3\), \(r \geq 1\)) ( or briefly MMD) is the result of assigning a direction to each edge of a k-partite multidigraph which is without loops and having at most r edges between every pair of vertices, one vertex from each part. We note that k-partite 1-digraph is an oriented k-partite graph and complete k-partite 1-digraph is a k-partite tournament. The case when k=1 gives multidigraph and when k=2 gives bipartite multidigraph, and these have been studied in [9]. Thus throughout this paper the MMD under discussion will have three or more than three parts. Let \(D(X_1, X_2, \cdots, X_k)\) (or briefly D) be an MMD with parts \(X_i = \{x_{i1}, x_{i2}, \cdots, x_{in_i}\}\), \(1 \leq i \leq k\). For any vertex \(x_{ij}\) in D, let \(d_{x_{ij}}^+\) and \(d_{x_{ij}}^-\) denote the outdegree and indegree. Define \(a_{x_{ij}}\) (or simply \(a_{ij}\))= \(d_{x_{ij}}^+ - d_{x_{ij}}^-\) as the imbalance of the vertiex \(x_{ij}\), where \(1 \leq j \leq n_i\). Note that we have \(1 \leq i \leq k\) and \(1 \leq j \leq n_i\), unless otherwise stated.

Let D be an MMD and \(x_{ij} \in X_i\), \(x_{mn} \in X_m\) and \(x_{st} \in X_s\), where \(i \neq m, m \neq s\) and \(s \neq i\). If there are f arcs directed from vertex \(x_{ij}\) to \(x_{mn}\) and g arcs directed from \(x_{mn}\) to \(x_{ij}\), with \(0 \leq f \leq r, 0 \leq g \leq r\) and \(0 \leq f + g \leq r\), it is denoted by \(x_{ij}(f - -g)x_{mn}\). An r-triple is an induced r-subdigraph of three vertices with one vertex from distinct part and is of the form \(x_{ij}(f_1 - -f_2)x_{mn}(g_1 - -g_2)x_{st}(h_1 - -h_2)x_{mn}\), where \(0 \leq f_1, f_2, g_1, g_2, h_1, h_2, f_1 + f_2, g_1 + g_2, h_1 + h_2 \leq r\). Also an oriented triple (or 1-triple) in D is an induced 1-subdigraph of three vertices, with one vertex each from distinct part. An oriented triple is said to be transitive if it is of the form \(x_{ij}(1 - -0)x_{mn}(1 - -0)x_{st}(0 - -1)x_{ij}\), or \(x_{ij}(1 - -0)x_{mn}(0 - -1)x_{st}(0 - -0)x_{ij}\), or \(x_{ij}(1 - -0)x_{mn}(0 - -0)x_{st}(0 - -0)x_{ij}\), or \(x_{ij}(1 - -0)x_{mn}(0 - -0)x_{st}(0 - -0)x_{ij}\), otherwise it is intransitive. An MMD D is said to be transitive if each of its oriented triple is transitive. In particular, an r-triple C in an MMD D is transitive if every oriented triple of C is transitive.

We have the following observation.

Theorem 4. Let D and D' be two MMD with the same imbalance sequences. Then D can be transformed to D' by successively transforming

(i) appropriate triples in one of the following ways.

Either (a) by changing an intransitive oriented triple(cyclic triple) \(x_{ij}(1-0)x_{mn}(1-0)x_{st}(1-0)x_{st}(1-0)x_{ij}\) to a transitive oriented triple \(x_{ij}(0-0)x_{mn}(0-0)x_{st}(0-0)x_{ij}\) which has the same imbalance sequences, or vice versa,

or (b) by changing an intransitive oriented triple \(x_{ij}(1-0)x_{mn}(1-0)x_{st}(0-0)x_{ij}\) to a transitive oriented triple \(x_{ij}(0-0)x_{mn}(0-0)x_{st}(0-1)x_{ij}\) which has the same imbalance sequences, or vice versa.

or (ii) by changing the symmetric arcs \(x_{ij}(1-1)x_{mn}\) to \(x_{ij}(0-0)x_{mn}\), which has the same imbalance sequences, or vice versa.

Proof. This can be easily established.

As a consequence of Theorem 3, we observe that among all MMD's having same imbalance sequences those with least number of arcs are transitive in nature.

Corollary 5. Among all MMD's with given imbalance sequences, those with the fewest arcs are transitive.

In an MMD, a vertex with indegree zero is called a transmitter. Evidently in a transitive oriented MMD with imbalance sequences Aⁱ = [ai1, ai2, · · · , ainⁱ ], any of the vertices with imbalances ainⁱ , can act as a transmitter.

The next result provides a useful recursive test of checking whether the sequences of integers are the imbalance sequences of an MMD.

The following result is a combinatorial criterion for determining whether k sequences of integers are realizable as imbalances.

Theorem 6. The k sequences of integers Aⁱ = [ai1, ai2, · · · , ainⁱ ], 1 ≤ i ≤ k, in non-decreasing order are imbalance sequences of an MMD if and only if

\[\sum_{j=1}^{m_1} a_{1j} + \sum_{j=1}^{m_2} a_{2j} + \dots + \sum_{j=1}^{m_k} a_{kj}\] \[\leq r \left[ m_1 \prod_{j=1, j \neq 1}^k (n_j - m_j) + m_2 \prod_{j=1, j \neq 2}^k (n_j - m_j) + \dots + m_k \prod_{j=1, j \neq k}^k (n_j - m_j) \right]\] (1)

or briefly

\[\sum_{i=1}^{k} \sum_{j=1}^{m_i} a_{ij} \le r \left[ \sum_{i=1}^{k} m_i \left( \prod_{j=1, j \ne i}^{k} (n_j - m_j) \right) \right],\]

for all sets of k integers mⁱ , 1 ≤ mⁱ ≤ nⁱ , with equality when mⁱ = nⁱ , for all i.

Proof. The necessity of the condition follows from the fact that a directed multipartite multi subgraph of an MMD induced by mⁱ vertices for all i, 1 ≤ i ≤ k, 1 ≤ mⁱ ≤ nⁱ has a sum of imbalances zero and these vertices can gather at most

\[r\left[m_1\prod_{j=1,j\neq 1}^k (n_j-m_j)+m_2\prod_{j=1,j\neq 2}^k (n_j-m_j)+\cdots+m_k\prod_{j=1,j\neq k}^k (n_j-m_j)\right]\]

imbalances from the remaining nⁱ − mⁱ vertices.

For sufficiency, assume that Aⁱ = [ai1, ai2, · · · , ainⁱ ] be k sequences of integers in non-decreasing order satisfying conditions (1) but are not imbalance sequences of any MMD. Let these sequences be chosen in such a way that nⁱ , are the smallest possible and a¹¹ is the least for the choice of nⁱ .

We consider the following two cases.

Case (i). Suppose equality in (1) holds for \(m_i \le n_j\), for \(1 \le j \le k\) so that

\[\sum_{j=1}^{m_1} a_{1j} + \sum_{j=1}^{m_2} a_{2j} + \dots + \sum_{j=1}^{m_k} a_{kj}\] \[= r \left[ m_1 \prod_{j=1, j \neq 1}^k (n_j - m_j) + m_2 \prod_{j=1, j \neq 2}^k (n_j - m_j) + \dots + m_k \prod_{j=1, j \neq k}^k (n_j - m_j) \right].\]

Consider the following k sequences.

\[A'_{1} = \left[a'_{1j}\right]_{j=1}^{m_{1}} = \left[a_{1j} - r \prod_{t=1, t \neq 1}^{k} (n_{t} - m_{t})\right]_{j=1}^{m_{1}},\] \[A'_{2} = \left[a'_{2j}\right]_{j=1}^{m_{2}} = \left[a_{2j} - r \prod_{t=1, t \neq 2}^{k} (n_{t} - m_{t})\right]_{j=1}^{m_{2}},\] \[\vdots\] \[A'_{k} = \left[a'_{kj}\right]_{j=1}^{m_{k}} = \left[a_{kj} - r \prod_{t=1, t \neq k}^{k} (n_{t} - m_{t})\right]_{j=1}^{m_{k}},\]

For \(1 \le r_i < m_i\) for all \(1 \le i \le k\), we have

\[\sum_{i=1}^{k} \sum_{j=1}^{r_i} a'_{ij} = \sum_{j=1}^{r_1} a'_{1j} + \sum_{j=1}^{r_2} a'_{2j} + \dots + \sum_{j=1}^{r_k} a'_{kj}\] \[= \sum_{j=1}^{r_1} \left( a_{1j} - r \prod_{t=1, t \neq 1}^{k} (n_t - m_t) \right) + \sum_{j=1}^{r_2} \left( a_{2j} - r \prod_{t=1, t \neq 2}^{k} (n_t - m_t) \right)\] \[+ \dots + \sum_{j=1}^{r_k} \left( a_{kj} - r \prod_{t=1, t \neq k}^{k} (n_t - m_t) \right)\] \[= \left( \sum_{j=1}^{r_1} a_{1j} + \sum_{j=1}^{r_2} a_{2j} + \dots + \sum_{j=1}^{r_k} a_{kj} \right)\] \[- r \left( r_1 \prod_{t=1, t \neq 1}^{k} (n_t - m_t) + r_2 \prod_{t=1, t \neq 2}^{k} (n_t - m_t) + \dots + r_k \prod_{t=1, t \neq k}^{k} (n_t - m_t) \right)\]

On imbalances in multipartite multidigraphs | U.T. Samee and S. Pirzada

\[\leq r \left( r_1 \prod_{j=1, j \neq 1}^k (n_j - r_j) + r_2 \prod_{j=1, j \neq 2}^k (n_j - r_j) + \dots + r_k \prod_{j=1, j \neq k}^k (n_j - r_j) \right)\] \[- r \left( r_1 \prod_{t=1, t \neq 1}^k (n_t - m_t) + r_2 \prod_{t=1, t \neq 2}^k (n_t - m_t) + \dots + r_k \prod_{t=1, t \neq k}^k (n_t - m_t) \right)\] \[\leq r \left( r_1 \prod_{t=1, t \neq 1}^k (m_t - r_t) + r_2 \prod_{t=1, t \neq 2}^k (m_t - r_t) + \dots + r_k \prod_{t=1, t \neq k}^k (m_t - r_t) \right)\] \[= r \sum_{i=1}^k r_i \left( \prod_{t=1, t \neq i}^k (m_t - r_t) \right)\]

and

\[\begin{split} &\sum_{i=1}^{k} \sum_{j=1}^{m_{i}} a'_{ij} = \sum_{j=1}^{m_{1}} a'_{1j} + \sum_{j=1}^{m_{2}} a'_{2j} + \dots + \sum_{j=1}^{m_{k}} a'_{kj} \\ &= \sum_{j=1}^{m_{1}} \left( a_{1j} - r \prod_{t=1, t \neq 1}^{k} (n_{t} - m_{t}) \right) + \sum_{j=1}^{m_{2}} \left( a_{2j} - r \prod_{t=1, t \neq 2}^{k} (n_{t} - m_{t}) \right) \\ &+ \dots + \sum_{j=1}^{m_{k}} \left( a_{kj} - r \prod_{t=1, t \neq k}^{k} (n_{t} - m_{t}) \right) \\ &= \left( \sum_{j=1}^{m_{1}} a_{1j} + \sum_{j=1}^{m_{2}} a_{2j} + \dots + \sum_{j=1}^{m_{k}} a_{kj} \right) \\ &- r \left( m_{1} \prod_{t=1, t \neq 1}^{k} (n_{t} - m_{t}) + m_{2} \prod_{t=1, t \neq 2}^{k} (n_{t} - m_{t}) + \dots + m_{k} \prod_{t=1, t \neq k}^{k} (n_{t} - m_{t}) \right) \\ &= r \left( m_{1} \prod_{j=1, j \neq 1}^{k} (n_{j} - m_{j}) + m_{2} \prod_{j=1, j \neq 2}^{k} (n_{j} - m_{j}) + \dots + m_{k} \prod_{j=1, j \neq k}^{k} (n_{j} - m_{j}) \right) \\ &- r \left( m_{1} \prod_{t=1, t \neq 1}^{k} (n_{t} - m_{t}) + m_{2} \prod_{t=1, t \neq 2}^{k} (n_{t} - m_{t}) + \dots + m_{k} \prod_{t=1, t \neq k}^{k} (n_{t} - m_{t}) \right) \\ &= r \sum_{i=1}^{k} m_{i} \left( \prod_{j=1, j \neq i}^{k} (n_{j} - m_{j}) \right) - r \sum_{i=1}^{k} m_{i} \left( \prod_{t=1, t \neq i}^{k} (n_{t} - m_{t}) \right) \\ &= 0. \end{split}\]

Thus the k sequences \(A_i' = \left[a_{ij}'\right]_{j=1}^{m_i}\), for all \(1 \le i \le k\) satisfy (1) and by the minimality of \(n_i\) the sequences \(A_i'\) are the imbalance sequences of some MMD \(D'(V_1', V_2', \cdots, V_k', E')\).

Now consider the following k sequences.

\[A_1'' == \left[ a_{1(m_1+j)} + r \prod_{t=1,t\neq 1}^k m_t \right]_{j=1}^{n_1}\] \[A_2'' = \left[ a_{2(m_2+j)} + r \prod_{t=1,t\neq 2}^k m_t \right]_{j=1}^{m_2},\] \[\vdots\] \[A_k'' = \left[ a_{k(m_k+j)} + r \prod_{t=1,t\neq k}^k m_t \right]_{j=1}^{m_k},\]

For all \(1 \le i \le k\) and \(1 \le r_i \le n_i - m_i\), we have

\[\sum_{i=1}^{k} \sum_{j=1}^{r_i} a_{ij}'' = \sum_{j=1}^{r_1} a_{1j}'' + \sum_{j=1}^{r_2} a_{2j}'' + \dots + \sum_{j=1}^{r_k} a_{kj}''\] \[= \sum_{j=1}^{r_1} \left( a_{1(m_1+j)} + r \prod_{t=1, t \neq 1}^{k} m_t \right) + \sum_{j=1}^{r_2} \left( a_{2(m_2+j)} + r \prod_{t=1, t \neq 2}^{k} m_t \right)\] \[+ \dots + \sum_{j=1}^{r_k} \left( a_{k(m_k+j)} + r \prod_{t=1, t \neq k}^{k} m_t \right)\]

\[\begin{split} &= \sum_{j=1}^{r_1} \left( a_{1(m_1+j)} + r \prod_{t=1,t \neq 1}^k m_t \right) + \sum_{j=1}^{r_2} \left( a_{2(m_2+j)} + r \prod_{t=1,t \neq 2}^k m_t \right) \\ &+ \dots + \sum_{j=1}^{r_k} \left( a_{k(m_k+j)} + r \prod_{t=1,t \neq k}^k m_t \right) \\ &= \left( \sum_{j=1}^{m_1+r_1} a_{1j} + \sum_{j=1}^{m_2+r_2} a_{2j} + \dots + \sum_{j=1}^{m_k+r_k} a_{kj} \right) \\ &- \left( \sum_{j=1}^{m_1} a_{1j} + \sum_{j=1}^{m_2} a_{2j} + \dots + \sum_{j=1}^{m_k} a_{kj} \right) \\ &+ r \left( r_1 \prod_{t=1,t \neq 1}^k m_t + r_2 \prod_{t=1,t \neq 2}^k m_t + \dots + r_k \prod_{t=1,t \neq k}^k m_t \right) \end{split}\]

Therefore

\[\begin{split} &\sum_{i=1}^k \sum_{j=1}^{r_i} a_{ij}'' \\ &\leq r(m_1 + r_1) \prod_{j=1, j \neq 1}^k (n_t - (m_t + r_t)) + r(m_2 + r_2) \prod_{j=1, j \neq 2}^k (n_t - (m_t + r_t)) \\ &+ \dots + r(m_k + r_k) \prod_{j=1, j \neq k}^k (n_t - (m_t + r_t)) \\ &- r \left( m_1 \prod_{t=1, t \neq 1}^k (n_t - m_t) + m_2 \prod_{t=1, t \neq 2}^k (n_t - m_t) + \dots + m_k \prod_{t=1, t \neq k}^k (n_t - m_t) \right) \\ &+ r \left( r_1 \prod_{t=1, t \neq 1}^k m_t + r_2 \prod_{t=1, t \neq 2}^k m_t + \dots + r_k \prod_{t=1, t \neq k}^k m_t \right) \\ &\leq r \left( r_1 \prod_{t=1, t \neq 1}^k (n_t - m_t - r_t) + r_2 \prod_{t=1, t \neq 2}^k (n_t - m_t - r_t) + \dots + r_k \prod_{t=1, t \neq k}^k (n_t - m_t - r_t) \right) \\ &= r \sum_{i=1}^k r_i \left( \prod_{t=1, t \neq i}^k (n_t - m_t - r_t) \right) \end{split}\]

with equality when \(r_i = n_i - m_i\) for all \(i, 1 \le i \le k\). Therefore by the minimality of \(n_i\), the k sequences \(A_i''\) form the imbalance sequences of some MMD \(D''(V_1'', V_2'', \dots, V_k'', E'')\).

Construct an MMD \(D(V_1, V_2, \dots, V_k, E)\) as follows.

Let \(V_1 = V_1' \cup V_1''\), \(V_2 = V_2' \cup V_2''\), \(\cdots\), \(V_k = V_k' \cup V_k''\) and \(V_i' \cap V_j'' = \phi\) for all i, j. The arc set E contains (a) all the arcs between \(V_i'\) and \(V_j'\), \(i \neq j\), (b) all arcs between \(V_i''\) and \(V_j''\), \(i \neq j\) and (c) r arcs from each vertex of \(V_i'\) to every vertex of \(V_i''\).

Then \(D(V_1, V_2, \dots, V_k)\) has imbalance sequences \(A_i\), which is a contradiction. Clearly this contradicts the given assumption.

Case (ii). Assume that the strict inequality holds in (1) for \(m_i \neq n_i\). Let \(A_1 = [a_{11} - 1, a_{12}, \cdots, a_{1(n_1-1)}, a_{1n_1} + 1]\) and Let \(A_j = [a_{j1}, a_{j2}, \cdots, a_{jn_j}]\) for all \(j, 2 \leq j \leq k\), so that \(A_i\) satisfy the conditions (1). Therefore by the minimality of \(a_{11}\), the sequences \(A_i\) are the imbalance sequences of some MMD \(D_1(Y_1, Y_2, \cdots, Y_k)\). Let \(a_{x_{11}} = a_{11} - 1\) and \(a_{x_{1n_1}} = a_{1n_1} + 1\). Since \(a_{x_{1n_1}} > a_{x_{11}} + 1\), there exists a vertex \(x_{jp}\) in \(Y_j\), \(2 \leq j \leq k\), \(1 \leq p \leq n_j\), such that \(x_{1n_1}(0 - 0)x_{jp}(1 - 0)x_{11}\), or \(x_{1n_1}(1 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(1 - 0)x_{jp}(1 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{jp}(0 - 0)x_{11}\), or \(x_{1n_1}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(0 - 0)x_{11}(\)

3. Imbalance sets in multipartite multidigraphs

The set of distinct imbalances of the vertices in an MMD is called its imbalance set. Now we give the existence of an MMD with a given imbalance set.

Theorem 8. Let \(P = \{p_1, p_2, \dots, p_m\}\) and \(Q = \{-q_1, -q_2, \dots, -q_n\}\), where \(p_1, p_2, \dots, p_m\), \(q_1, q_2, \dots, q_n\) are positive integers with \(p_1 < p_2 < \dots < p_n\) and \(q_1 < q_2 < \dots < q_n\) and the greatest common divisor \((p_1, p_2, \dots, p_m, q_1, q_2, \dots, q_n) = t\), where \(1 \le t \le r\). Then there exists an MMD with imbalance set \(P \cup Q\).

Proof. Since \((p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_n) = t\) there exist positive integers \(f_1, f_2, \cdots, f_m, g_1, g_2, \cdots, g_n\) with \(f_1 < f_2 < \cdots < f_m\) and \(g_1 < g_2 < \cdots < g_n\) such that \(p_i = tf_i\) for \(1 \le i \le m\) and \(q_j = tg_j\) for \(1 \le j \le n\). First assume that k is even, say k = 2s where \(s \ge 1\). Construct an MMD \(D(X_1, X_2, \cdots, X_k)\) as follows. Let

\[X_{1} = X_{11} \cup X_{12} \cup \cdots \cup X_{1m} \cup X_{1}^{1} \cup X_{1}^{2} \cup \cdots \cup X_{1}^{n},\] \[X_{2} = X_{21} \cup X_{22} \cup \cdots \cup X_{2m} \cup X_{2}^{1} \cup X_{2}^{2} \cup \cdots \cup X_{2}^{n},\] \[X_{3} = X_{31} \cup X_{32} \cup \cdots \cup X_{3m} \cup X_{3}^{1} \cup X_{3}^{2} \cup \cdots \cup X_{3}^{n},\]

\(X_{2s} = X_{2s1} \cup X_{2s2} \cup \cdots \cup X_{2sm} \cup X_{2s}^1 \cup X_{2s}^2 \cup \cdots \cup X_{2s}^n,\)

with \(X_{ij} \cap X_{uv} = \emptyset\), \(X_{ij} \cap X_u^v = \emptyset\), \(X_i^j \cap X_u^v = \emptyset\), \(|X_{1i}| = g_1\) for all \(i, 1 \le i \le m\), \(|X_1^i| = g_i\) for all \(i, 1 \le i \le n\), \(|X_{2i}| = f_i\) for all \(i, 1 \le i \le m\), \(|X_2^i| = f_1\) for all \(i, 1 \le i \le n\), \(|X_{i1}| = g_1\) for all odd \(i, 3 \le i \le 2s - 1\), and \(|X_{i1}| = f_1\) for all even \(i, 4 \le i \le 2s\). Let there be t arcs directed from each vertex of \(X_{1i}\) to every vertex of \(X_{2i}\) for all \(1 \le i \le m\); t arcs directed from each vertex of \(X_{1i}^i\) to every vertex of \(X_{2i}^i\) to every vertex of \(X_{2i}^i\) for all odd \(i, 3 \le i \le 2s - 1\) so that we obtain 2s-partite r-digraph MMD with imbalance of vertices as follows.

For \[1 \leq i \leq m\], \[a_{x_{1i}} = t|X_{2i}| - 0 = tf_i = p_i, \ for \ all \ x_{1i} \in X_{1i};\] for \(1 \leq j \leq n\), \[a_{x_1^i} = t|X_2^i| - 0 = tf_1 = p_1, \ for \ all \ x_1^i \in X_1^i;\] for \(1 \leq j \leq m\), \[a_{x_{2i}} = 0 - t|X_{1i}| = -tg_1 = -q_1, \ for \ all \ x_{2i} \in X_{2i};\] for \(1 \leq j \leq n\), \[a_{x_2^i} = 0 - t|X_1^i| = -tg_i = -q_i, \ for \ all \ x_2^i \in X_2^i;\] for all odd \(i, 3 \leq i \leq 2s - 1\) \[a_{x_{i1}} = t|X_{(i+1)1}| - 0 = tf_1 = p_1, \ for \ all \ x_{i1} \in X_{i1};\]

and for even i, 4 ≤ i ≤ 2s,

\[a_{x_{i1}} = 0 - t|X_{(i-1)1}| = -tg_1 = -q_1, \text{ for all } x_{i1} \in X_{i1}.\]

Therefore imbalance set of D(X1, X2, · · · , Xk) is P ∪ Q.

By using the same argument as above, it can be shown that the result holds for odd k also. Hence the proof is complete.

Acknowledgements

The authors are grateful to the anonymous referee for useful comments. The research of second author (S. Pirzada) is supported by SERB-DST, New Delhi under the research project number EMR/2015/001047/MS.

References

• [1] Zhou Guofei and S. Pirzada, Degree sequences in oriented k-hypergraphs, J. Applied Math. Comput. 27 (2008), 149–158.
• [2] A. Ivanyi, S. Pirzada and F.A. Dar, Tripartite graphs with given degree set, Acta Univ. Sap. Informatica 7 (1) (2015), 72–106.
• [3] K.K. Kayibi and M.A. Khan and S. Pirzada, Uniform sampling of k-hypertournaments, Linear and Multilinear Algebra 61 (1) (2013), 123–138.
• [4] M.A. Khan, S. Pirzada and K.K. Kayibi, Scores, inequalities and regular hypertournaments, J. Math. Ineq. Appl. 15 (2) (2012), 343–351.
• [5] D. Mubayi, T.G. Will and D.B. West, Realizing degree imbalances in directed graphs, Discrete Math. 239 (2001), 147–153.
• [6] S. Pirzada, On imbalances in digraphs, Krujagevac J. Math. 31 (2008), 143-146.
• [7] S. Pirzada, U. Samee, T.A. Naikoo and A. Ivanyi, Imbalances in multidigraphs, Acta Univ. Sapien. Mathematica 2 (2) (2010), 133–145.
• [8] S. Pirzada, T.A. Naikoo and N.A. Shah, Imbalances in oriented tripartite graphs, Acta Mathematica Sinica 27 (5) (2011), 927–932.
• [9] S. Pirzada, A.M. Al-Assaf and K.K. Kayibi, Imbalances in oriented multipartite graphs, Acta Univ. Sapientiae, Mathematica 3 (1) (2011), 34–42.
• [10] S. Pirzada, A. Ivanyi and N.A. Shah, Imbalances of bipartite multitournaments, Annales Univ. Sci. Budapest., Sect. Comp. 36 (2012), 2151–228.
• [11] S. Pirzada, K. Kayibi and N.A. Shah, Tripartite multi digraphs and imbalances, Kragujevic J. Math. 36 (1) (2012), 85–94.

• [12] S. Pirzada, An Introduction to Graph Theory, Universities Press, OrientBlackswan, Hyderabad (2012).
• [13] S. Pirzada and T.A. Naikoo, Score sets in tournaments, Vietnam J. Math. 34 (2) (2006), 157– 161.
• [14] S. Pirzada, T.A. Naikoo and N.A. Shah, Score sequences in oriented graphs, J. Appl. Math. Comp. 23 (1) (2007), 257–268.
• [15] S. Pirzada and U. Samee, Mark sequences in digraphs, Sminaire Lotharingien de Combinatoire 55 (2013), B55c.
• [16] S. Pirzada, A. Ivanyi and M.A. Khan, Score sets and kings, Algorithms of Informatics 3 (2013), 1410–1450.
• [17] S. Pirzada and T.A. Naikoo, Inequalities for marks in digraphs, J. Math. Ineq. Appl. 9 (2) (2006), 189–198.
• [18] S. Pirzada and T.A. Naikoo, Score sets in oriented graphs, Appl. Anal. Disc. Math. 2 (2008), 107–113.
• [19] S. Pirzada, T.A. Chishti and T.A. Naikoo, Score lists in [h,k] bipartite hypertournaments, Discrete Math. Appl. 19 (3) (2009), 321– 328.
• [20] S. Pirzada and Zhou Guofei, Score sequences in oriented k-hypergraphs, European J. Pure Appl. Math. 1 (3) (2008), 10–20.
• [21] S. Pirzada, Degree sequences in multi hypertournaments, Appl. Math.: J. Chinese Universities 24 (3) (2009), 350–354.
• [22] S. Pirzada and Zhou Guofei, Score lists in (h,k)-bipartite hypertournaments, Appl. Math., J. Chinese Universities, Series B 22 (4) (2007), 485–489.
• [23] S. Pirzada, Score lists in bipartite multi hypertournaments, Math. Vesnik 64 (4) (2012), 286– 296.
• [24] S. Pirzada and T.A. Naikoo, Tournaments, oriented graphs and football sequences, Acta. Univ. Sap. Math. 9 (1) (2017), 213–223.
• [25] S. Pirzada and T.A. Naikoo, Mark sets in 2-digraphs, Appl. Comput. Math. 10 (2) (2011), 283–288.
• [26] S. Pirzada, On scores in multipartite hypertournaments, Eurasian Math. J. 2 (1) (2011), 112– 119.
• [27] U. Samee and T.A. Chishti, On imbalances in oriented bipartite graphs, Eurasian Math. J. 1 (2) (2010), 136–141.