# The Minimum Size of Digraphs Satisfying Directed Cut Conditions

Authors: Huawen Ma
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

A directed graph (digraph)D of order n satisfies directed cut condition DCC if there are at least S arcs from any set S⊆VD, S≤n/2 to its complement S¯=VD/S. We show that a digraph D of even order n has at least 2n−3 arcs if D satisfies DCC.


---

## Body

## 1. Introduction

A network is made up of nodes and links between nodes. Suppose that a cluster ofk hosts in one part of the network wishes to communicate with k hosts at another part of the network. Assume that any two communication paths can use common intermediate nodes, but no two communication paths between distinct pairs can share common links. Then, there must exist at least k links leaving the cluster. A simple graph can quite naturally represent this communication network. Path-pairability is a notion that emerged from this practical networking problem introduced by Csaba et al. [1] and further studied by Faudree et al. [2–4]. A graph G of even order n is path-pairable, if for any set of disjoint pairs si,ti, 1≤i≤n/2, G has pairwise edge disjoint si,ti-paths. A series of problems on path-pairable graphs have been proposed, such as seeking diameter, maximum order, and maximum degree. In [4], Faudree et al. considered the problem of investigating the minimum size of path-pairable graph G of order n. It is trivial that EG≥n−1 as K1,n−1 is path-pairable. They showed that |EG|≥3n/2−logn−O1 for path-pairable graph G with ΔG<n−1.A graph onn vertices satisfies cutconditionCC, if for any S⊆VG, S≤n/2, there are at least S edges between S and S¯=VG/S. Obviously, a path-pairable graph satisfies CC, but the inverse is not. Jobson et al. [5] proved that a graph G of even order n with ΔG<n−1, if G satisfies CC, then EG≥3n/2−3, and this bound is tight. A graph of even order n satisfies even cut conditionECC, if for any S⊆VG, S=n/2, there are at least n/2 edges between S and S¯. Jobson et al. [5] showed that if G is a graph of order n≡0 (mod 4) with ΔG<n−1 and satisfies ECC, then |EG|≥5n/4−2.On account of the results of Jobson et al., we consider the minimum size of the digraphs satisfying directed cut condition in this paper. LetD be a digraph with vertex set VD and arc set ED. For any two disjoint sets A,B⊆VD, let eA,B denote the number of arcs from A to B in D. We say a digraph D on n vertices satisfies directedcutconditionDCC, if eS,S¯≥S for any S⊆VD with S≤n/2.LetD1 be a digraph with n vertices and VD1=u∪S, where S is an independent set with n−1 vertices in D1. In D1, u directs to each vertex of S and each vertex in S directs to u. Let D2 be a digraph with n (even) vertices and VD2=u∪v∪S∪T, where S and T are two independent sets with n/2−1 vertices in D2. In D2, u directs to each vertex of S and each vertex in S directs to v; v directs to each vertex of T and each vertex in T directs to u; u directs to v and v directs to u. It is easy to verify that D1 and D2 with size 2n−2 arcs satisfy DCC, which implies that the minimum size of digraphs satisfying DCC is at most 2n−2, whether the maximum degree is 2n−2 or not. The following theorem gives that each digraph with n (even) vertices satisfying DCC has at least 2n−3 arcs.Theorem 1.1.
LetD be a digraph of even order n. If D satisfies DCC, then D has at least 2n−3 arcs.Remark 1.2.
We do not know whether there is a digraph which has2n−3 arcs and satisfy DCC. But by the digraphs D1 and D2, we know 2n−3 or 2n−2 is the tight value.
Corresponding to theECC of undirected graphs, we say a digraph D of even order n satisfies evendirectedcutconditionEDCC, if eS,S¯≥n/2 for any S⊆VD with S=n/2.Theorem 1.3.
LetD be a digraph of even order n. If D satisfies EDCC, then D has at least 2n−n arcs.We say a digraphD satisfies weakly even directedcut conditionWEDCC, if maxeS,S¯,eS¯,S≥n/2 for any S⊆VD with S=n/2. Let D3 be an orientation of K1,n−1 such that the apex directs to other vertices. Clearly, D3 has n−1 arcs and satisfies WEDCC. Hence, we limit the maximum degree of digraphs. Using the probabilistic method, we give the following result.Theorem 1.4.
LetD be a digraph of even order n. For any 0<ϵ≤1, if ΔD≤ϵ2n/128 and D satisfies WEDCC, then D has at least 2n−2n/1+ϵ arcs.The rest of this paper is organized as follows. In the next section, we state some notations and lemmas used. In Section3, we give a proof of Theorem 1.1. In Section 4, we prove Theorems 1.3 and 1.4. The final section contains some concluding remarks.


## 2. Notations and Lemmas

We consider digraphs without loops and parallel arcs, but the reverse parallel arcs are allowed. We first introduce some notations and definitions. LetD be a digraph with vertex set VD and arc set ED, and let eD=ED. Given x,y∈VD, we write xy for the arc directed from x to y. We call vertex y as an outneighbour of x and x as an inneighbour of y. For any vertex v∈VD, let ND+v be the outneighbours set of v in D, and let dD+v=ND+v be the outdegree of v. Similarly, we write ND−v as the in-neighbours set of v in D and dD−v=ND−v as the indegree of v. Let NDv=ND+v∪ND−v be the set of neighbours of v and dDv=dD+v+dD−v be degree of v. Let Δ+D, Δ−D, ΔD, and δD be the maximumoutdegree, maximumindegree, maximumdegree, and minimumdegree of D, respectively. When understood, the subscript may be dropped. For any digraph D, we can associate a simple graph G on the same vertex set by replacing each arc by an edge and deleting parallel edges if there are. Such a simple graph G is called underlyinggraph of D. We also call as digraph Dk-connected if its underlying graph G is k-connected. For a digraph D, we call V1,V2 a partition of D if V1∪V2=VD and V1∩V2=∅. Let eV1,V2 denote the number of arcs from V1 to V2 and eVi be the number of arcs such that two ends lie in Vi, i=1,2. Let DVi denote the induced subdigraph of Vi.Now, we state several theorems which will be used in the following proofs. The first one is a well-known result on partitioning due to Lóvasz [6]: if G is a 2-connected graph of order a1+a2, where a1, a2 are positive integers, then G has a partition VG=A1∪A2 such that Ai induces a connected subgraph of order ai, i=1,2. The following result introduced in [7] is stronger than Lóvasz’s, which plays a key role in our proofs.Lemma 2.1 (see [7]).
IfG is a 2-connected graph of order n, then VG has a labeling v1,v2,…,vn such that for every 1<i<n, vi has a neighbour in both v1,…,vi−1 and vi+1,…,vn.Abisection of a graph G is a partition of VG=V1∪V2 such that ‖V1−V2‖≤1. We use Gc to denote the complement of a graph G. The next lemma on minimum bisection due to Fan et al. [8] has strong correlation with our problems.Lemma 2.2 (see [8]).
LetM be a maximum matching in Gc of a graph G which has n vertices and m edges. Then, G admits a bisection V1,V2 such that eV1,V2≤m+⌊n/2⌋−|M|/2.We introduce the well-known Azuma–Hoeffding inequality [9, 10] and use the version given in the book (see Corollary 2.27) of Janson et al. [11].Lemma 2.3 (see [11]).
LetZ1,Z2,…,Zn be independent random variables taking values in 1,2,…,k, let Z:=Z1,Z2,…,Zn, and let f:1,2,…,k⟶N such that |fY−fY′|≤ci for any Y,Y′∈1,2,…,kn which differ only in the ith coordinate. Then, for any z>0,(1)PrfZ≥EfZ+z≤exp−z22∑i=1nci2,PrfZ≤EfZ−z≤exp−z22∑i=1nci2.


## 3. Proof of Theorem 1.1

Proof.
LetD be a digraph of n (even) vertices satisfying DCC. Suppose on the contrary that eD<2n−3. We may suppose that D is not 2-connected. For otherwise, by Lóvasz’s theorem, D has a bisection V1,V2 such that DV1 and DV2 induce two connected subdigraphs, respectively. By DCC, eV1,V2≥n/2 and eV2,V1≥n/2. So,(2)eD≥eV1+eV2+eV1,V2+eV2,V1≥2×n2−1+2×n2≥2n−2,a contradiction.
SinceD is not 2-connected, D has cut vertices. Let u be a cut vertex of D and C1,C2,…,Ckk≥2 be connected components of D−u. Then, by DCC, we have a simple fact: for any Ci with Ci≤n/2, and for any v∈VCi, vu∈ED.
We first claim thatd−u≠n−1. Suppose for the contradiction that d−u=n−1, if there exists a component, say C1, with order larger than n/2, then eVD∖VC1,VC1=eu,VC1≥n−C1 by DCC. Thus,(3)eD≥eC1+∑i=2keCi+eVD,VC1,VC1+d−u≥C1−1+n−C1+n−1=2n−2,a contradiction. So, we suppose that Ci≤n/21≤i≤k. Without loss of generality, let Ck=maxC1,C2,…,Ck. We split C1,C2,…,Ck−1=A1∪A2 such that A1 and A2 are as close as possible. Then, we partition VCk−v into two sets B1, B2 such that A1+B1=n/2−1, where v is an arbitrary vertex of Ck. Let E1=A1∪B1, E2=A2∪B2. Let a1=eu,E1, a2=eu,E2, b1=eB1,B2, b2=eB2,B1, c1=eB1,v, and c2=eB2,v. Define(4)d=0,uv∈ED,1,otherwise.
ByDCC, for bisections VD=E1∪u,E2∪v and VD=E2∪u,E1∪v, we have(5)eE1∪u,E2∪v=eu,E2+eB1,B2+eB1,v+d=a2+b1+c1+d≥n2.
Similarly,(6)eE2∪u,E1∪v=eu,E1+eB2,B1+eB2,v+d=a1+b2+c2+d≥n2.
Adding up (5) and (6), we obtain that(7)a1+a2+b1+b2+c1+c2≥n−2.
Thus,eD≥d−u+a1+a2+b1+b2+c1+c2≥2n−3, a contradiction.
Now, we suppose thatd−u<n−1. Then, there is exact one component of D−u which has order larger than n/2. We call such a subdigraph the largecomponent at u and denote it by Lu. We claim that all cut vertices of D are contained in one block; we call it centralblock of D. Assume it is not true. Then, there must exist cut vertices x1, x2, and x3 and blocks B1, B2, B3, and B4 such that xi∈Bi∩Bi+1 for i=1,2,3. B1 and B4 belong to different components of D−x2, and then there must exist a block which does not belong to the large component at x2, say B1. That is to say, each vertex of the component containing B1 directs to x2 by the fact we mentioned above. Then, removing the cut vertex x1 cannot separate B1 and B2, a contradiction.
LetB be the central block of D (if D has only one cut vertex u, then let B:=Lu+u.). We define a weight for each vertex x of B as follows:(8)ωx=|VD−VLx|,ifxis a cut vertex,1,otherwise.
By the definition ofωx, it is easy to see ωx<n/2 for each x∈B.
SinceB is a block of D, by Lemma 2.1, B has a labeling v1,v2,…,vB such that for each 1<i<B, vi has a neighbour in both sets v1,…,vi−1 and vi+1,…,vB. Choose the smallest number k such that w1=∑i=1k−1ωvi≤n/2 and ∑i=1kωvi=w1+ωvk>n/2. Let(9)W1=∪VB′|B′≠Bis a block andB′∩v1,…,vk−1≠∅.
According to the definition of weight value of vertices ofB, we can easily find that W1=w1.
We claim thatw1=W1<n/2. For otherwise, partition VD into two sets, W1 and VD∖W1, which induce two connected subdigraphs by Lemma 2.1. Thus, by DCC, we have(10)eD=eW1+eVD\W1+eW1,VD,W1+eVD,W1,W1,≥2×n2−1+2×n2≥2n−2,a contradiction.
We haveωvk≥2 as w1<n/2 and w1+ωvk>n/2. That is to say, vk is a cut vertex of D. Let(11)W2=∪VB′|B′≠Bis a block andB′∩vk+1,…,vB≠∅.
Then,W2≠∅ as w1+ωvk<n. Let W0=VD/W1∪W2, then blocks containing vk are contained in W0. Let vk=u and v be an arbitrary vertex of W0∖u. Partition W0/u,v into two sets W01, W02 such that W01+W1=n/2−1, then W02+W2=n/2−1.
Leteu,W1∪W01=α1, eu,W2∪W02=α2; let eW1∪W01,u=β1, eW2∪W02,u=β2; let eW1∪W01,W2∪W02=eW01,W02=γ1, eW2∪W02,W1∪W01=eW02,W01=γ2; let ev,W01=δ1, ev,W02=δ2; and let eW01,v=θ1, eW02,v=θ2.
For bisectionsVD=W1∪W01∪u,W2∪W02∪v and VD=W1∪W01∪v,W2∪W02∪u, by DCC, we have(12)eW1∪W01∪u,W2∪W02∪v=eW1∪W01,W2∪W02+eW1∪W01,v+eu,W2∪W02+d=γ1+θ1+α2+d≥n2,eW2∪W02∪v,W1∪W01∪u=eW2∪W02,W1∪W01+eW2∪W02,u+ev,W1∪W01+1=γ2+β2+δ1+1≥n2,eW1∪W01∪v,W2∪W02∪u=eW1∪W01,W2∪W02+eW1∪W01,u+ev,W2∪W02+1=γ1+β1+δ2+1≥n2,and(13)eW2∪W02∪u,W1∪W01∪v=eW2∪W02,W1∪W01+eW2∪W02,v+eu,W1∪W01+d=γ2+θ2+α1+d≥n2.
Adding up (12) and (13), we obtain that(14)α1+α2+β1+β2+γ1+γ2+δ1+δ2+θ1+θ2≥2n−2−2d−γ1+γ2.
Recall thatωvk<n/2, then |W0|≤n/2. Considering the partition VD=W0,VD∖W0, by DCC, we have(15)eW0,VD,W0≥W0=W01+W02+2.
Note that the subdigraphs induced byWi for i=1,2 are connected and each vertex of W0∖u directs to u. Thus, by (14), we have(16)eD≥W1−1+W2−1+W0−1+∑i=12αi+βi−W0i+γi+θi+δi+d≥n−3+2n−2−2d−γ1+γ2−W0−2+d≥2n−3+n−d−W0−γ1−γ2.
IfW0+γ1+γ2≤n−1, then eD≥2n−3, we are done. So, we suppose that W0+γ1+γ2≥n. Thus,(17)eD≥W1−1+W2−1+eW0,u,u+eu,W1∪W2+γ1+γ2≥W1−1+W2−1+W0−1+W0+γ1+γ2≥n−3+n=2n−3,a contradiction too.


## 4. Proofs of Theorems 1.3 and 1.4

Proof of Theorem 1.3.
LetD be a digraph with n vertices which satisfies EDCC, and let G be the underlying graph of D and M be the maximum matching of Gc. We need to show that eD≥2n−n. We may suppose that M≥n−2n+1/2. For otherwise, we have ωG=n−2M≥2n. Hence, eD≥eG≥2n2n−1/2=2n−n, we are done.
Suppose on the contrary thateD<2n−n. Then, by Lemma 2.2,D admits a bisection VD=V1∪V2 such that(18)eV1,V2≤eD+n/2−M4<2n−n+n/2−n−2n+1/24<n2,a contradiction with EDCC.
Now, we prove Theorem1.4 using the probabilistic method.Lemma 4.1.
LetD be a digraph with n (even) vertices and m arcs, G be the underlying graph of D, and M be a maximum matching of Gc, then D admits a bisection VD=V1∪V2 such that(19)maxeV1,V2,eV2,V1≤m/4+n/4−M/2+R,where R=2∑v∈VDd2v.Proof.
LetM=u1v1,u2v2,…,uM/2vM/2. We know G−VM is a clique, as M is a maximum matching of Gc. Let uM/2+1vM/2+1,…,un/2vn/2 be a perfect matching of G−VM. Partition VD into n/2 disjoint pairs u1,v1,u2,v2,…,un/2,vn/2. Let Z=Z1,Z2,…,Zn/2 be a random, independent, and uniform 2-coloring (with color 1 and 2) of u1,u2,…,un/2, and color each vi with 3−Zi for 1≤i≤n/2. For i=1,2, let(20)Vi=v∈VD|vwas coloredi.
Thus,VD=V1∪V2 is a bisection of D.
Now, we boundEeV1,V2. For each arc e=uv∈ED, let Ie be the indicator random variable of the event e∈EV1,V2. If the endpoints u, v of e were paired in the beginning, i.e., u,v=ui,vi for some M/2<i≤n/2, then Pre∈EV1,V2=1/2. Otherwise,(21)Pre∈EV1,V2=Pru∈V1,v∈V2=Pru∈V1Prv∈V2=14.
Obviously, there are at most2×n/2−M arcs which were paired in the beginning. By linearity of expectation, we have(22)EeV1,V2=∑e∈EDEIe≤n−2M2+m−n+2M4=m4+n4−M2.
By symmetry, we also haveEeV2,V1≤m/4+n/4−M/2. Note that changing the color of any vertex ui for 1≤i≤n/2 cannot affect eV1,V2,eV2,V1 by more than dui+dvi. Define(23)L=∑i=1n/2dui+dvi2.
Then, we have(24)L≤2∑i=1n/2d2ui+d2vi=2∑v∈VDd2v.
By Lemma2.3, we obtain(25)PreV1,V2≥EeV1,V2+R≤exp−R22L≤e−1,and(26)PreV2,V1≥EeV2,V1+R≤exp−R22L≤e−1.
Hence, there is a bisectionVD=V1∪V2 of D such that(27)maxeV1,V2,eV2,V1≤m4+n4−M2+R.
According to Lemma4.1, we can easily obtain a fact: if m<n+2M−4R, then D admits a bisection VD=V1∪V2 such that maxeV1,V2,eV2,V1<n/2.Lemma 4.2.
LetD be a digraph with n (even) vertices and m≥n arcs. Let G be the underlying graph of D and M be a maximum matching of Gc. For 0<ϵ≤1, if Δ≤ϵ2n/128 and m<n+2M/1+ϵ, then maxeV1,V2,eV2,V1<n/2.Proof.
Note thatR=2∑v∈VDd2v≤2Δ∑v∈VDdv=22Δm≤ϵm/4, since m<n+2M/1+ϵ, which implies m<n+2M−ϵm<n+2M−4R. By the fact mentioned above, we have maxeV1,V2,eV2,V1<n/2.Proof of Theorem 1.4.
We may suppose thatM>n/2−n. For otherwise, |VG−VM|≥2n and VG−VM is a clique. Hence,(28)eD≥eG≥eG−VM=2n2n−12=2n−n.
We are done. SinceM>n/2−n, by Lemma 4.2 and WEDCC, we have eD≥n+2M/1+ϵ≥2n−2n/1+ϵ.


## 5. Concluding Remarks and Open Problems

We in this paper consider extremum problems in directed graphs and give some lower bounds of arcs when a digraph satisfiesDCC, EDCC, and WEDCC, respectively. Below, we give some comments on these results and propose some open problems.For Theorem1.1, 2n−3 or 2n−2 could be the exact value although we do not know which one to be. Considering the symmetry of this condition, we prefer to believe that it is an even number. Hence, we propose the following conjecture.Conjecture 5.1.
LetD be a digraph of order n. If D satisfies DCC, then eD≥2n−2.For Theorem1.3, it is a corollary of Lemma 2.2. In fact, EDCC is closely related to the minimum cut. Obviously, if a digraph with maximum indegree or outdegree n−1, then it must satisfy WEDCC. It is not clear to us what the exact value is when the maximum indegree and outdegree are smaller than n−1.Problem 5.2.
What is the minimum size of a digraph which satisfiesEDCC?Problem 5.3.
LetD be a digraph D with Δ+D<n−1 and Δ−D<n−1. What is the minimum size of D when D satisfies WEDCC?



---

*Source: 5815591-2022-02-14.xml*