On imbalances in oriented multipartite graphs

On imbalances in oriented multipartite graphs

S. Pirzada

King Fahd University of Petroleum and Minerals

Dhahran, Saudi Arabia email:[email protected]

Abdulaziz M. Al-Assaf

King Fahd University of Petroleum and Minerals

Dhahran, Saudi Arabia email:alassaf@[email protected]

Koko K. Kayibi

King Fahd University of Petroleum and Minerals Dhahran, Saudi Arabia

email:[email protected]

Abstract. An orientedk-partite graph(multipartite graph) is the result of assigning a direction to each edge of a simple k-partite graph. Let

D(V1, V2,· · · , Vk)be an orientedk-partite graph, and let d⁺_vij and d⁻_vij

be respectively the outdegree and indegree of a vertexvij in Vi. Define bv_ij (or simplybij asbij =d⁺_vij−d⁻_vijas the imbalance of the vertexvij. In this paper, we characterize the imbalances of orientedk-partite graphs and give a constructive and existence criteria for sequences of integers to be the imbalances of some oriented k-partite graph. Also, we show the existence of an orientedk-partite graph with the given imbalance set.

1 Introduction

A digraph without loops and without multi-arcs is called a simple digraph.

Mubayi et al. [1] defined the imbalance of a vertex v_i in a digraph as b_vi (or simply bi) = d⁺_vi −d⁻_vi, where d⁺_vi and d⁻_vi are respectively the outdegree and indegree of v_i. The imbalance sequence of a simple digraph is formed by

2010 Mathematics Subject Classification:05C20

Key words and phrases:digaph, imbalance, outdegree, indegree, oriented graph, oriented multipartite graph, arc

34

listing the vertex imbalances in non-increasing order. A sequence of integers F = [f₁, f₂,· · · , f_n] with f₁ ≥f₂ ≥ · · · ≥f_n is feasible if it has sum zero and satisfiesPk

i=1f_i≤k(n−k), for1≤k < n.

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

Theorem 1 A sequence is realizable as an imbalance sequence if and only if it is feasible.

The above result is equivalent to saying that a sequence of integers B = [b₁, b2,· · ·, bn]withb1≥b2≥ · · · ≥bnis an imbalance sequence of a simple digraph if and only if for 1≤k < n

Xk i=1

b_i≤k(n−k),

with equality whenk=n.

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

Theorem 2 A sequence of integersB= [b₁, b₂,· · · , b_n]withb₁≤b₂≤ · · · ≤ bnis an imbalance sequence of a simple digraph if and only if for1≤k < n

Xk i=1

bi≥k(n−k),

with equality when k=n.

Various results for imbalances in digraphs and oriented graphs can be found in [2, 3, 4, 5].

2 Imbalance sequences in oriented multipartite graphs

An oriented multipartite (k-partite) graph is the result of assigning a direction to each edge of a simple multipartite (k-partite) graph,k≥2. Throughout this paper we denote an orientedk-partite graph byk-OG, unless otherwise stated.

LetV_i={v_i1, v_i2,· · ·, v_ini},1≤i≤k, be kparts of k-OG D(V₁, V₂,· · ·, V_k),

and letd⁺_vij andd⁻_vij,1≤j≤n_i, be respectively the outdegree and indegree of a vertexv_ijinV_i. Defineb_vij (or simplyb_ijasb_ij=d⁺_v

ij−d⁻_v

ij as the imbalance of the vertex vij. The sequences Bi= [b_i1, bi2,· · ·, bin_i], 1 ≤ i ≤ k, in non- decreasing order are called the imbalance sequences of D(V₁, V₂,· · ·, V_k).

The k sequences of integers B_i = [b_i1, b_i2,· · ·, b_ini], 1 ≤ i ≤ k, in nonde- creasing order are said to be realizable if there exists ank-OG with imbalance sequences B_i, 1≤ i≤k. Various criterions for imbalance sequences in k-OG can be found in [2].

For any two vertices vij in Vi and vlm in Vl (i 6= l, 1 ≤ i ≤ l ≤ k, 1 ≤ j≤n_i,1≤m≤n_l) of k-OG D(V₁, V₂,· · ·, V_k), we have one of the following possibilities.

(i). An arc directed from vijtovlm, denoted byvij(1−0)v_lm. (ii). An arc directed fromv_lmtov_ij, denoted by v_ij(0−1)v_lm.

(iii). There is no arc from v_ijto v_lmand there is no arc from v_lmto v_ijand this is denoted by vij(0−0)v_lm.

A triple in k-OG is an induced suboriented graph of three vertices with exactly one vertex from each part. For any three vertices v_ij,v_lmand v_pqin k-OG D, the triples of the form vij(1−0)v_lm(1−0)v_pq(1−0)v_ij, or vij(1− 0)v_lm(1−0)v_pq(0−0)v_ijare said to be oriented intransitive, while as the triples of the formv_ij(1−0)v_lm(1−0)v_pq(0−1)v_ij, orv_ij(1−0)v_lm(0−1)v_pq(0−0)v_ij, or v_ij(1−0)v_lm(0−0)v_pq(0−1)v_ij, or v_ij(1−0)v_lm(0−0)v_pq(0−0)v_ij, or v_ij(0−0)v_lm(0−0)v_pq(0−0)v_ijare said to be oriented transitive. Ank-OG is said to be oriented transitive if all its triples are oriented transitive, otherwise oriented intransitive.

We have the following observation.

Theorem 3 Let D and D^′be two k-OG with the same imbalance sequences.

Then D can be transformed to D^′ by successively transforming appropriate triples in one of the following ways. Either (a) by changing a cyclic triple v_ij(1−0)v_lm(1−0)v_pq(1−0)v_ijto an oriented transitive triplev_ij(0−0)v_lm(0−

0)v_pq(0−0)v_ijwhich has the same imbalance sequences, or vice versa, or (b) by changing an oriented intransitive triple v_ij(1−0)v_lm(1−0)v_pq(0−0)v_ij to an oriented transitive triple v_ij(0−0)v_lm(0−0)v_pq(0−1)v_ij which has the same imbalance sequences, or vice versa.

Proof. Let B_i be the imbalance sequences of k-OG D whose parts are V_i, 1 ≤ i ≤ k and |V_i| = n_i. Let D^′ be k-OG with parts V_i^′, 1 ≤ i ≤ k. To prove the result, it is sufficent to show that D^′ can be obtained from D by successively transforming triples in any one of the ways as given in (a), or (b).

We fix n_i, 2 ≤ i ≤ k and use induction on n₁. For n₁ = 1, the result is obvious. Assume that the result holds when there are fewer than n₁ vertices in the first part. Let j₂, j₃,· · · , j_kbe such that forl₂> j₂, l₃> j₃,· · ·, l_k> j_k, 1 ≤j₂ < l₂ ≤n₂, 1 ≤j₃ < l₃ ≤n₃,· · · , 1 ≤j_k< l_k≤n_k, the corresponding arcs have the same orientations inDandD^′. Forj₂, j₃,· · · , j_kand2≤i, p, q≤ k,p6=q, we have three cases to consider.

(i). v_1n1(1−0)v_ijp(1−0)v_ijq and v^′_1n

1(0−0)v^′_ij

p(0−0)v^′_ij

q, (ii). v_1n1(0− 0)v_ijp(0−1)v_ijq andv^′_1n

1(1−0)v^′_ij

p(0−0)v^′_ij

q and (iii).v_1n1(1−0)v_ijp(0−0)v_ijq and v^′_1n

1(0−0)v^′_ij

p(0−1)v^′_ij

q. Case (i).Sincev_1n1 andv^′_1n

1 have equal imbalances, we havev_1n1(0−1)v_ijq andv^′_1n

1(0−0)v^′_ij

q, orv_1n1(0−0)v_ijq andv^′_1n

1(1−0)v^′_ij

q. Thus there is a triple v_1n1(1−0)v_ijp(1−0)v_ijq(1−0)v_1n1, or v_1n1(1−0)v_ijp(1−0)v_ijq(0−0)v_1n1 in D, and corresponding to these v^′_1n

1(0− 0)v^′_ij

p(0− 0)v^′_ij

q(0 −0)v^′_1n

1, or v^′_1n

1(0−0)v^′_ij

p(0−0)v^′_ij

q(0−1)v^′_1n

1 respectively is a triple inD^′. Case (ii).Sincev_1n1 andv^′_1n

1have equal imbalances, we havev_1n1(1−0)v_ijq andv^′_1n

1(0−0)v^′_ij

q. Thus there is a triplev_1n1(0−0)v_ijp(0−1)v_ijq(0−1)v_1n1 inDand corresponding to thisv^′_1n

1(1−0)v^′_ij

p(0−0)v^′_ij

q(0−0)v^′_1n

1 is a triple inD^′.

Case (iii). Since v_1n1 and v^′_1n

1 have equal imbalances, therefore we have v_1n1(0−1)v_ijq andv^′_1n

1(0−0)v^′_ij

q. Thus v_1n1(1−0)v_ijp(0−0)v_ijq(1−0)v_1n1 is a triple inD, and corresponding to this v^′_1n

1(0−0)v^′_ij

p(0−1)v^′_ij

q(0−0)v^′_1n

1

is a triple in D^′.

Therefore from (i), (ii) and (iii) it follows that there is an k-OG that can be obtained from D by any one of the transformations (a) or (b) with the imbalances remaining unchanged. Hence the result follows by induction.

Corollary 1 Among all k-OG with given imbalance sequences, those with the fewest arcs are oriented transitive.

A transmitter is a vertex with indegree zero. In a transitive oriented k-OG with imbalance sequences B_i = [b_i1, b_i2,· · · , b_ini], 1 ≤ i ≤ k, any of the vertices with imbalances b_ini, 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 k-OG.

Theorem 4 LetBi= [b_i1, bi2,· · · , bin_i],1≤i≤k, beksequences of integers in non-decreasing order with b1n₁ > 0 and bjn_j ≤ Pk

r=1,r6=jnr, for all j, 2 ≤ i ≤ k. Let B^′₁ be obtained from B₁ by deleting one entry b_1n1, and let

B^′₂, B^′₃,· · · , B^′_k, be obtained from B₂, B₃,· · · , B_k by increasing b_1n1 smallest entries of B₂, B₃,· · · , B_k by one each. Then B_i are imbalance sequences of some k-OG if and only if B^′_iare imbalance sequences.

Proof. Suppose B^′_ibe the imbalance sequences of some k-OG D^′ with parts V_i^′,1≤i≤k. Thenk-OGDwith imbalance sequencesBican be obtained by adding a vertexv_1n1 inV₁^′ such thatv_1n1(1−0)v_ijfor those verticesv_ijinV_i^′, i6=1 whose imbalances are increased by one in going fromB_itoB^′_i.

Conversely, let Bi be the imbalance sequences of k-OG D with parts Vi, 1 ≤ i ≤ k. By Corollary 4, any of the vertices v_ini in V_i with imbalances b_ini, 1 ≤ i ≤ k can be a transmitter. Assume that the vertex v_1n1 in V₁ with imbalance b1n₁ be a transmitter. Clearly, d⁺_v

1n1 > 0 and d⁻_v

1n1 = 0 so that b_1n1 = d⁺_v

1n1 −d⁻_v

1n1 > 0. Also, d⁺_v

jnj ≤ Pk

r=1,r6=jn_r and d⁻_v

jnj ≥ 0 for 2≤i≤kso that b_jnj =d⁺_v

jnj −d⁻_v

jnj ≤Pk

r=1,r6=jn_r.

LetUbe the set ofv_1n1 vertices of smallest imbalances inV_j,2≤i≤kand let W =V₂∪V₃∪ · · · ∪V_k−U. Now construct Dsuch that v_1n1(1−0)ufor all uinU. ClearlyD−{v_1n1}realizes V_i^′,1≤i≤k.

Theorem 5 provides an algorithm for determining whether or not the se- quences B_i, 1 ≤i ≤ k of integers in non-decreasing order are the imbalance sequences and for constructing a corresponding k-OG.

SupposeB_i= [b_i1, b_i2,· · · , b_ini],1≤i≤k, be imbalance sequences ofk-OG with parts V_i = {v_i1, v_i2,· · ·, v_ini}, where b_1n1 > 0 and b_jnj ≤ Pk

r=1,r6=jn_r, 2≤i≤k. Deletingb_1n1 and increasingb_1n1 smallest entries ofB₂, B₃,· · · , B_k by 1 each to form B^′₂, B^′₃,· · ·, B^′_k. Then arcs are defined by v1n₁(1 −0)v_ij, for which b^′_vij = b_vij + 1, where i 6= 1. If at least one of the conditions b_1n1 > 0, or b_jnj ≤ Pk

r=1,r6=jn_r does not hold, then we delete b_ini for that i for which the conditions get satisfied and the same argument is used for defining arcs. If this method is applied recursively, then (i) it tests whetherB_i are the imbalance sequences, and if B_iare the imbalance sequences (ii) k-OG

△(B_i) with imbalance sequencesB_iis constructed.

We illustrate this reduction and resulting construction as follows.

Consider the four sequencesB₁= [1, 3, 4],B₂= [−3, 2, 2],B₃= [−4,−3]and B₄= [−3, 1].

(i) [1, 3, 4],[−3, 2, 2],[−4,−3],[−3, 1]

(ii)[1, 3],[−2, 2, 2],[−3,−2],[−2, 1],v₁₃(1−0)v₂₁,v₁₃(1−0)v₃₁,v₁₃(1−0)v₃₂, v₁₃(1−0)v₄₁

(iii)[1],[−1, 2, 2],[−2,−1],[−2, 1],v12(1−0)v₂₁,v12(1−0)v₃₁,v12(1−0)v₃₂ (iv) ∅,[−1, 2, 2],[−2,−1],[−2, 1],v₁₁(1−0)v₃₁

(v)∅,[−1, 2],[0,−1],[−1, 1],v₂₃(1−0)v₃₁,v₂₃(1−0)v₄₁or,∅,[−1, 2],[−1, 0], [−1, 1]

(vi)∅,[−1],[0, 0],[0, 1],v₂₂(1−0)v₃₂,v₂₂(1−0)v₄₁ (vii)∅,[0],[0, 0],[0, 0],v₄₂(1−0)v₂₁.

Clearly 4-OG with parts V₁ = {v₁₁, v₁₂, v₁₃}, V₂ = {v₂₁, v₂₂, v₂₃}, V₃ = {v₃₁, v32} and V4 = {v₄₁, v42} in which v13(1−0)v₂₁, v13(1−0)v₃₁, v13(1− 0)v₃₂,v₁₃(1−0)v₄₁,v₁₂(1−0)v₂₁,v₁₂(1−0)v₃₁,v₁₂(1−0)v₃₂,v₁₁(1−0)v₃₁, v₂₃(1−0)v₃₁,v₂₃(1−0)v₄₁,v₂₂(1−0)v₃₂,v₂₂(1−0)v₄₁,v₄₂(1−0)v₂₁are arcs has imbalance sequences[1, 3, 4],[−3, 2, 2],[−4,−3]and [−3,−1].

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

Theorem 5 LetB_i= [b_i1, b_i2,· · · , b_ini],1≤i≤k, beksequences of integers in non-decreasing order. Then B_i are the imbalance sequences of some k-OG if and only if

Xk

i=1 mi

X

j=1

b_ij≥2

k−1X

i=1

Xk j=i+1

m_im_j− Xk

i=1

n_i Xk

j=1

m_j− Xk

i=1

m_in_i, (1)

for all sets of k integers mi, 0≤mi≤niwith equality when mi=ni. Proof. The necessity of the condition follows from the fact that the k-OG induced by m_ivertices for 1≤ i≤k,1 ≤m_i≤n_i has a sum of imbalances 2Pk−1

i=1

Pk

j=i+1m_im_j−Pk

i=1n_iPk

j=1m_j−Pk

i=1m_in_i.

For sufficiency, assume that Bi = [b_i1, bi2,· · ·, bin_i], 1 ≤ i ≤ k be the sequences of integers in non-decreasing order satisfying conditions (1) but are not the imbalance sequences of any k-OG. Let these sequences be chosen in such a way thatni,1≤i≤kare the smallest possible andb11is the least for the choice of n_i. We consider the following two cases.

Case (i). Suppose equality in (1) holds for some m_j ≤n_j, 1≤ i≤ k−1, mk≤nk, so that

Xk i=1

mi

X

j=1

b_ij=2

k−1X

i=1

Xk j=i+1

m_im_j− Xk i=1

n_i Xk

j=1

m_j− Xk

i=1

m_in_i.

By the minimality of n_i, 1 ≤i ≤k the sequencesB^′_i= [b_i1, b_i2,· · · , b_imi] are the imbalance sequences of somek-OG D^′(V₁^′, V₂^′,· · · , V_k^′).

Define B^′′_i = [b_i(m

i+1), b_i(mi+2),· · · , b_i(ni)],1≤i≤k.

Consider the sum Xk

i=1 fi

X

j=1

b_i(mi+j)= Xk i=1

mXi+fi

j=1

b_ij− Xk

i=1 mi

X

j=1

b_ij

≥2

k−1X

i=1

Xk j=i+1

(m_i+f_i)(m_j+f_j) − Xk i=1

n_i Xk

j=1

(m_j+f_j)

− Xk

i=1

(m_i+fi)n_i−2 Xk−1

i=1

Xk j=i+1

mimj+ Xk i=1

ni

Xk j=1

mj+ Xk

i=1

mini

=2

k−1X

i=1

Xk j=i+1

m_im_j+2 Xk−1

i=1

Xk j=i+1

(m_if_j+f_im_j+f_if_j) − Xk i=1

n_i Xk

j=1

f_j

− Xk

i=1

m_in_i− Xk

i=1

f_in_i−2

k−1X

i=1

Xk j=i+1

m_im_j+ Xk

i=1

n_i Xk

j=1

m_j+

+ Xk

i=1

mini≥2

k−1X

i=1

Xk j=i+1

fifj− Xk i=1

ni

Xk j=1

fj− Xk

i=1

fini,

for 1 ≤ f_i≤ n_i−m_i, with equality when f_i= n_i−m_ifor all i, 1 ≤ i≤ k.

So by the minimality of n_i, 1≤i ≤k, the sequences B^′′_i form the imbalance sequence of some k-OGD^′′(V₁^′′, V₂^′′,· · · , V_k^′′).

Construct a new k-OG D(V₁, V₂,· · ·, V_k) as follows. Let V₁ = V₁^′ ∪ V₁^′′, V₂ = V₂^′ ∪V₂^′′,· · ·V_k = V_k^′ ∪V_k^′′ with V_i^′∩V_i^′′ = ∅ and the arc set con- taining those arcs which are amongV₁^′, V₂^′,· · · , V_k^′ and amongV₁^′′, V₂^′′,· · ·, V_k^′′. Then D(V₁, V₂,· · · , V_k) has imbalance sequences B_i, 1 ≤ i ≤ k, which is a contradiction.

Case (ii).Assume that the strict inequality holds in (1) for somem_i6=n_i, 1≤i≤k. Let B^′₁= [b₁₁−1, b₁₂,· · · , b_1n1−1, b_1n1]and let B^′_j= [b_j1, b_j2,· · ·, b_jnj]for allj,2≤j≤k. Clearly the sequencesB^′_i,1≤i≤ksatisfy conditions (1). Therefore, by the minimality of b₁₁, the sequences B^′_i,1 ≤i≤kare the imbalance sequences of somek-OGD^′(V₁^′, V₂^′,· · · , V_k^′). Letbv₁₁ =b₁₁−1and b_v1n1 =b_1n1+1. Sinceb_v1n1 > b_v11+1, there exists a vertex v_ijeither inV_i, 1≤i≤k,1≤j≤n_i, such that v_1n1(0−0)v_ij(1−0)v₁₁, or v_1n1(1−0)v_ij(0− 0)v₁₁, orv1n₁(1−0)v_ij(1−0)v₁₁, orv1n₁(0−0)v_ij(0−0)v₁₁inD^′(V₁^′, V₂^′,· · ·, V_k^′), and if these are changed tov_1n1(0−1)v_ij(0−0)v₁₁, orv_1n1(0−0)v_ij(0−1)v₁₁, orv_1n1(0−0)v_ij(0−0)v₁₁, orv_1n1(0−1)v_ij(0−1)v₁₁respectively, the result is k-OG with imbalance sequences Bi, which is a contradiction. This completes

the proof.

3 Imbalance sets in oriented multipartite graphs

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

Theorem 6 Let S = {s₁, s2,· · ·, sn} and T = {−t₁,−t₂,· · ·,−t_n}, where s₁, s₂,· · ·, s_n, t₁, t₂,· · · , t_n are positive integers with s₁ < s₂ < · · · < s_n and t₁< t₂<· · ·< t_n. Then there exists k-OG with imbalance set S∪T.

Proof.First assume thatk≥2is even. Constructk-OGD(V₁, V2,· · ·, Vk)as follows. Let

V₁=V₁₁∪V₁₂∪ · · · ∪V_1n, V₂=V₂₁∪V₂₂∪ · · · ∪V_2n,

. . .

V_k=V_k1∪V_k2∪ · · · ∪V_kn,

with V_ij∩V_lm = ∅, |V_ij| = t_i for all odd i, 1 ≤ i ≤ k−1, 1 ≤ j ≤ n and

|V_ij| = sifor all even i, 2≤i ≤k, 1≤j ≤ n. Let there be an arc from each vertex of V_ij to every vertex ofV_(i+1)j for all oddi, 1≤i≤k−1,1≤j≤n so that we obtain k-OG with imbalance of vertices as follows.

For odd i,1≤i≤k−1 and 1≤j≤n

b_vij =|V_(i+1)j|−0=s_i, for all v_ij∈V_ij; and for eveni,2≤i≤kand 1≤j≤n

b_vij =0−|V_(i+1)j|= −t_i, for all v_ij∈V_ij

Therefore imbalance set ofD(V₁, V₂,· · · , V_k) isS∪T.

Now assumek≥3is odd. Construct k-OGD(V₁, V₂,· · · , V_k) as below. Let V₁=V₁₁∪V₁₁^′ ∪V₁₂∪V₁₂^′ ∪. . .∪V_1n∪V_1n^′ ,

V₂=V₂₁∪V₂₂∪. . .∪V_2n, . . .

Vk−1=V_(k−1)1∪V_(k−1)2∪. . .∪V_(k−1)n, V_k=V_k1^′ ∪V_k2^′ ∪. . .∪V_kn^′ ,

withV_ij∩V_lm=∅,V_ij^′ ∩V_lm^′ =∅,V_ij∩V_lm^′ =∅,|V_ij|=t_ifor alli,1≤i≤k−2, 1 ≤ j ≤ n, |V_ij| = s_i for all even i, 2 ≤ i ≤ k−1, 1 ≤ j ≤ n, |V_ij^′| = t_i for all j, 1 ≤j ≤ n and |V_kj^′ | = s_j for all j, 1 ≤j ≤ n. Let there be an arc from each vertex ofV_ijto every vertex of V_(i+1)jfor all i,1≤i≤k−2,1≤j ≤n and let there be an arc from each vertex ofV_1j^′ to every vertex ofV_kj^′ for allj, 1≤j≤n, so that we obtain k-OG with imbalance setS∪T, as above.

References

[1] D. Mubayi, T. G. Will, D. B. West, Realizing degree imbalances in directed graphs,Discrete Math.,239(2001), 147–153.

[2] S. Pirzada, On imbalances in digraphs, Kragujevac J. Math., 31 (2008), 143–146.

[3] S. Pirzada, T. A. Naikoo, U. Samee, A. Iv´anyi, Imbalances in multidi- graphs,Acta Univ. Sapientiae, Math.,2 (2010), 137–146.

[4] S. Pirzada, T. A. Naikoo, N. A. Shah, Imbalances in oriented tripartite graphs,Acta Math. Sinica,27(2011), 927–932.

[5] U. Samee, T. A. Cahisti, On imbalances in oriented bipartite graphs, Eurasian Math. J.,1 (2010), 136–141.

Received: October 20, 2010