- Email: [email protected]

Degree sequence conditions for maximally edge-connected oriented graphs Lutz Volkmann Lehrstuhl II f¨ur Mathematik, RWTH Aachen University, 52056 Aachen, Germany Received 18 November 2005; accepted 23 January 2006

Abstract If D is a digraph, δ(D) its minimum degree and λ(D) its edge-connectivity, then λ(D) ≤ δ(D). A digraph D is called maximally edge-connected if λ(D) = δ(D). A digraph without any directed cycle of length 2 is called an oriented graph. Sufficient conditions for digraphs to be maximally edge-connected have been given by several authors. However, closely related conditions for maximally edge-connected oriented graphs have received little attention until recently. In this work we will present some degree sequence conditions for oriented graphs as well as for oriented bipartite graphs to be maximally edge-connected. c 2006 Elsevier Ltd. All rights reserved. Keywords: Oriented graph; Edge-connectivity; Degree sequence; Oriented bipartite graph

1. Introduction and terminology We consider finite digraphs without loops and multiple edges. A digraph without any directed cycle of length 2 is called an oriented graph. For a digraph D the vertex set is denoted by V (D) and the edge set (or arc set) by E(D). + (v) be its We define the order of D by n = n(D) = |V (D)|. For a vertex v ∈ V (D) of a digraph D, let d + (v) = d D − − out-degree and d (v) = d D (v) its in-degree. The degree of a vertex u of a digraph D, denoted by d(u) = d D (u), is the minimum of its out-degree and its in-degree. The degree sequence of D is defined as the nonincreasing sequence of the degrees of the vertices of D. The minimum out-degree and minimum in-degree of a digraph D are denoted by + − δ + = δ (D) and δ − = δ (D) and δ = δ(D) = min{δ + (D), δ − (D)} is its minimum degree. A digraph D is strongly connected or simply strong if for every pair u, v of vertices there exists a directed path from u to v in D. A digraph D of order n ≥ 2 is k-edge-connected if for any set S of at most k −1 edges the subdigraph D − S is strong. The edge-connectivity λ = λ(D) of a digraph D is defined as the largest value of k such that D is k-edge-connected. Because λ(D) ≤ δ(D), we call a digraph D maximally edge-connected if λ(D) = δ(D). For two disjoint vertex sets X and Y of a digraph D let (X, Y ) be the set of edges from X to Y . For other graph theory terminology we follow Chartrand and Lesniak [4]. Sufficient conditions for digraphs to be maximally edge-connected were given by several authors, for example by Balbuena and Carmona [2], Balbuena et al. [3], Dankelmann and Volkmann [5], F`abrega and Fiol [6], Geller

E-mail address: [email protected] c 2006 Elsevier Ltd. All rights reserved. 0893-9659/$ - see front matter doi:10.1016/j.aml.2006.01.011

1256

L. Volkmann / Applied Mathematics Letters 19 (2006) 1255–1260

and Harary [7], Hellwig and Volkmann [8,9], Imase et al. [10], Jolivet [11] and Xu [12]. However, closely related conditions for maximally edge-connected oriented graphs have received little attention until recently. In this work we will present some degree and degree sequence conditions for oriented graphs and oriented bipartite graphs to be maximally edge-connected. Examples will demonstrate that the results obtained are best possible in some sense. 2. Maximally edge-connected oriented graphs We start with a simple but useful observation. Lemma 2.1. Let D be an oriented graph of edge-connectivity λ and minimum degree δ ≥ 1. If λ < δ, then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| = λ such that |X|, |Y | ≥ 2δ + 1. Proof. Let X, Y ⊂ V (D) be two disjoint sets with X ∪ Y = V (D) such that |(X, Y )| = λ. By reason of symmetry we only show that |X| ≥ 2δ + 1. If we suppose to the contrary that |X| ≤ 2δ, then we arrive at the contradiction |X|(|X| − 1) |X|δ ≤ |X|δ + ≤ + λ ≤ δ(|X| − 1) + δ − 1. d + (x) ≤ 2 x∈X Corollary 2.2 (Ayoub and Frisch [1] 1970). If D is an oriented graph with minimum degree δ(D) ≥ (n(G) − 1)/4, then λ(D) = δ(D). Let D be an arbitrary digraph of order n and degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ ≥ 1. If δ ≥ n/2 or if δ ≤ n/2 − 1 and k (di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 1 i=1

for some integer k with 1 ≤ k ≤ δ, then Dankelmann and Volkmann [5] have proved that λ = δ. For oriented graphs the following weaker condition implies λ = δ. Theorem 2.3. Let D be an oriented graph of order n, edge-connectivity λ and degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ ≥ 1. If δ ≥ (n − 1)/4 or if δ ≤ (n − 1)/4 − 1 and k (di + dn+i−2δ−1 ) ≥ k(n − k − 1) + 2δ − 1 i=1

for some integer k with 1 ≤ k ≤ 2δ + 1, then λ = δ. Proof. Suppose to the contrary that λ < δ. According to Lemma 2.1, there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| = λ < δ such that |X|, |Y | ≥ 2δ + 1. This implies that δ ≤ (n − 1)/4 − 1. Now let S ⊂ X and T ⊂ Y be two k-sets with 1 ≤ k ≤ 2δ + 1. Since D contains no directed cycles of length two and since there are at most δ − 1 edges from X to Y , we deduce that |S|(|S| − 1) + |S|(|X| − |S|) + δ − 1 d + (v) ≤ 2 v∈S k 1 = k |X| − − + δ − 1. 2 2 Similarly we obtain 1 k − +δ−1 d (v) ≤ k |Y | − − 2 2 v∈T and thus in total d(v) ≤ k (n − k − 1) + 2δ − 2. v∈S∪T

(1)

L. Volkmann / Applied Mathematics Letters 19 (2006) 1255–1260

1257

Now we choose S and T to contain the k vertices in X and in Y of highest degree, respectively. Then S ∪ T contains the k vertices of highest degree but not the 2δ + 1 − k vertices of lowest degree in D. This implies that v∈S∪T

d(v) ≥

k

(di + dn+i−2δ−1 ).

i=1

However, combining the last inequality together with (1), we obtain a contradiction to our hypothesis.

If there are n/2 disjoint pairs of vertices (vi , wi ) in an arbitrary digraph D of order n with d(vi ) + d(wi ) ≥ n for all i = 1, 2, . . . , n/2 , then Xu [12] has proved in 1994 that λ(D) = δ(D). Applying Theorem 2.3, we will show that a corresponding weaker condition leads to a maximally edge-connected oriented graph. Corollary 2.4. Let D be an oriented graph of order n, minimum degree δ and edge-connectivity λ. If there are n/2 − 1 disjoint pairs of vertices (vi , wi ) for i = 2, 3, . . . , n/2 with d(vi ) + d(wi ) ≥ n − 2δ and a further pair (v1 , w1 ) such that d(v1 ) + d(w1 ) ≥ n − 2δ − 1, then λ = δ. Proof. If δ ≥ (n − 1)/4, then λ = δ by Corollary 2.2. If δ ≤ (n − 1)/4 − 1, then from the n/2 pairs of vertices , w ) containing the 2δ vertices of lowest degree of v and w . This leads choose 2δ pairs (v1 , w1 ), (v2 , w2 ), . . . , (v2δ i i 2δ to 2δ 2δ (di + dn+i−2δ−1 ) ≥ (d(vi ) + d(wi )) i=1

i=1

≥ 2δ(n − 2δ) − 1 = 2δ(n − 2δ − 1) + 2δ − 1. Now Theorem 2.3 with k = 2δ yields the desired identity λ = δ.

The following family of examples will demonstrate that the degree sequence condition in Theorem 2.3 is best possible in the sense that k (di + dn+i−2δ−1 ) ≥ k(n − k − 1) + 2δ − 2 i=1

for some k with 1 ≤ k ≤ 2δ + 1 does not guarantee that the oriented graph is maximally edge-connected. Example 2.5. Let p ≥ 1 be an integer, and let T1 and T2 be two p-regular tournaments of order 2 p + 1 with vertex sets V (T1 ) = {x 1 , x 2 , . . . , x 2 p+1 } and V (T2 ) = {y1 , y2 , . . . , y2 p+1 }. Now we define the tournament T as the disjoint union of T1 and T2 together with the edge set S = {x 1 y1 , x 2 y2 , . . . , x p−1 y p−1 } and all further edges from T2 to T1 . Then T is of order 4 p + 2 with δ(T ) = dT (x i ) = dT (yi ) = p for p ≤ i ≤ 2 p + 1 and dT (x i ) = dT (yi ) = p + 1 for 1 ≤ i ≤ p − 1. It follows that 2δ+1

(di + dn+i−2δ−1 ) = 2 p( p + 2) + 2( p + 1)( p − 1)

i=1

= (2δ(T ) + 1)(n(T ) − (2δ(T ) + 1) − 1) + 2δ(T ) − 2. However, since the set S is an edge-cut of the tournament T , we observe that λ(T ) = p − 1 < p = δ(T ). Example 2.5 also shows that Corollary 2.4 is best possible.

1258

L. Volkmann / Applied Mathematics Letters 19 (2006) 1255–1260

3. Maximally edge-connected oriented bipartite graphs Lemma 3.1. Let D be an oriented bipartite graph of edge-connectivity λ and minimum degree δ ≥ 1. If λ < δ, then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| = λ such that |X|, |Y | ≥ 4δ. Proof. Let X, Y ⊂ V (D) be two disjoint sets with X ∪ Y = V (D) such that |(X, Y )| = λ. By reason of symmetry we only show that |X| ≥ 4δ. If we suppose to the contrary that |X| ≤ 4δ − 1, then we obtain |X|δ ≤ |X|δ + ≤

d + (x) ≤

x∈X

|X|(4δ − 1) |X|2 +λ≤ + δ − 1. 4 4

It follows that |X| ≤ 4δ − 4 and thus |X|(4δ − 4) |X|2 |X|δ ≤ |X|δ + ≤ +λ≤ + δ − 1. d + (x) ≤ 4 4 x∈X This leads to |X| ≤ δ − 1, a contradiction to Lemma 2.1.

Corollary 3.2. If D is an oriented bipartite graph, then λ(D) = δ(D) when n(G) + 1 . δ(D) ≥ 8 Theorem 3.3. Let D be an oriented bipartite graph of order n, edge-connectivity λ and degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ ≥ 1. If δ ≥ (n + 1)/8 or if δ ≤ (n + 1)/8 − 1 and 2k (di + dn+i−4δ ) ≥ k(n − 2k) + 2δ − 1 i=1

for some integer k with 1 ≤ k ≤ 2δ, then λ = δ. Proof. Suppose to the contrary that λ < δ. According to Lemma 3.1, there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| = λ < δ such that |X|, |Y | ≥ 4δ. This implies that δ ≤ (n + 1)/8 − 1. If V and V is a bipartition of D, then we define by X = X ∩ V , X = X ∩ V , Y = Y ∩ V and Y = Y ∩ V . First we show that X , X , Y and Y contain at least δ + 1 vertices. Clearly, we have |X |, |X |, |Y |, |Y | ≥ 1. Suppose that |X | ≤ δ. Since D contains no directed cycles of length two, we deduce that δ|X | + δ|X | ≤ δ + |X| ≤ d + (v) ≤ |X ||X | + λ ≤ δ|X | + δ − 1, v∈X

and thus we arrive at the contradiction δ ≤ δ|X | ≤ δ − 1. Analogously one can show that |X |, |Y |, |Y | ≥ δ + 1. Now we distinguish two cases. Case 1. Assume that |X |, |X | ≥ k. Let S ⊆ X and S ⊆ X be such that |S | = |S | = k and S = S ∪ S . It follows that d + (v) ≤ k 2 + k(|X | − k + |X | − k) + λ ≤ k(|X| − k) + δ − 1. (2) v∈S

Case 2. Assume that |X | = k − t for 1 ≤ t ≤ k/2. Now let S = X and S ⊆ X such that |S | = k + t and S = S ∪ S . It follows that d + (v) ≤ (k + t)(k − t) + (k − t)(|X | − k − t) + λ v∈S

≤ k|X | − t|X | + δ − 1 = k(|X| − k) − k|X | + k 2 − t|X | + δ − 1 = k(|X| − k) + δ − 1 + kt − t|X | ≤ k(|X| − k) + δ − 1.

Hence we see that inequality (2) is also valid in this case.

L. Volkmann / Applied Mathematics Letters 19 (2006) 1255–1260

1259

Similarly we can choose T ⊆ Y with |T | = 2k such that d − (v) ≤ k(|Y | − k) + δ − 1.

(3)

v∈T

Adding (2) and (3), we obtain d(v) ≤ k (n − 2k) + 2δ − 2.

(4)

v∈S∪T

Now we choose S and T to contain the 2k vertices in X and in Y of highest degree, respectively. Then S ∪ T contains the 2k vertices of highest degree but not the 4δ − 2k vertices of lowest degree in D. This implies that v∈S∪T

d(v) ≥

2k

(di + dn+i−4δ ).

i=1

Combining the last inequality with (4), we obtain a contradiction to our hypothesis.

Next we present a family of examples which demonstrate that Theorem 3.3 is also the best possible. Example 3.4. Let p ≥ 1 be an integer, and let B1 and B2 be two p-regular bipartite tournaments of order 4 p with bipartition X , X and Y , Y such that X = {x 1 , x 2 , . . . , x 2 p } and Y = {y1 , y2 , . . . , y2 p }. Now we define the bipartite tournament B with the bipartition X ∪ Y and X ∪ Y as the disjoint union of B1 and B2 together with the edge set S = {x 1 y1 , x 2 y2 , . . . , x p−1 y p−1 } and all further possible edges from B2 to B1 . Then B is of order 8 p with d B (x i ) = d B (yi ) = p + 1 for 1 ≤ i ≤ p − 1 and δ(B) = d B (v) = p for all other vertices v ∈ V (B). It follows that 4δ (di + dn+i−4δ ) = ( p + 1)(2 p − 2) + p(6 p + 2) i=1

= 2δ(T )(n(T ) − 4δ(T )) + 2δ(T ) − 2. However, since the set S is an edge-cut of the bipartite tournament B, we observe that λ(B) = p − 1 < p = δ(B). Corollary 3.5. Let D be an oriented bipartite graph of even order n, minimum degree δ and edge-connectivity λ. If there are n/2 disjoint pairs of vertices (vi , wi ) with n+1 − 2δ 2 for i = 1, 2, . . . , n/2 , then λ = δ. d(vi ) + d(wi ) ≥

Proof. If δ ≥ (n + 1)/8, then λ = δ by Corollary 3.2. If δ ≤ (n + 1)/8 − 1, then from the n/2 pairs of vertices , w ) containing the 4δ vertices of lowest degree of v and w . This leads choose 4δ pairs (v1 , w1 ), (v2 , w2 ), . . . , (v4δ i i 4δ to 4δ 4δ (di + dn+i−4δ ) ≥ (d(vi ) + d(wi )) i=1

i=1

n+1 − 2δ ≥ 4δ 2 = 2δ(n − 4δ) + 2δ.

Now Theorem 3.3 with k = 2δ yields the desired identity λ = δ.

Remark 3.6. If D is an oriented bipartite graph of odd order n, minimum degree δ ≥ 2, and there exist n/2 − 1 disjoint pairs of vertices (vi , wi ) with d(vi ) + d(wi ) ≥ (n + 3)/2 − 2δ for i = 1, 2, . . . , n/2 − 1, then Theorem 3.3 with k = 2δ − 1 leads similarly to λ = δ.

1260

L. Volkmann / Applied Mathematics Letters 19 (2006) 1255–1260

References [1] J.N. Ayoub, I.T. Frisch, On the smallest-branch cuts in directed graphs, IEEE Trans. Circuit Theory CT-17 (1970) 249–250. [2] C. Balbuena, A. Carmona, On the connectivity and superconnectivity of bipartite digraphs and graphs, Ars Combin. 61 (2001) 3–21. [3] C. Balbuena, A. Carmona, J. F`abrega, M.A. Fiol, On the connectivity and the conditional diameter of graphs and digraphs, Networks 28 (1996) 97–105. [4] G. Chartrand, L. Lesniak, Graphs and Digraphs, 3rd edition, Chapman & Hall, 1996. [5] P. Dankelmann, L. Volkmann, Degree sequence conditions for maximally edge-connected graphs and digraphs, J. Graph Theory 26 (1997) 27–34. [6] J. F`abrega, M.A. Fiol, Bipartite graphs and digraphs with maximum connectivity, Discrete Appl. Math. 69 (1996) 271–279. [7] D. Geller, F. Harary, Connectivity in digraphs, in: Recent Trends in Graph Theory (Proc. 1st New York City Graph Theory Conf. 1970), in: Lecture Notes in Mathematics, vol.186, 1971, pp. 105–115. [8] A. Hellwig, L. Volkmann, Maximally edge-connected digraphs, Australas. J. Combin. 27 (2003) 23–32. [9] A. Hellwig, L. Volkmann, Neighborhood conditions for graphs and digraphs to be maximally edge-connected, Australas. J. Combin. 33 (2005) 265–277. [10] M. Imase, T. Soneoka, K. Okada, Connectivity of regular directed graphs with small diameters, IEEE Trans. Comput. 34 (1985) 267–273. [11] J.L. Jolivet, Sur la connexit´e des graphes orient´es, C. R. Acad. Sci. Paris 274 A (1972) 148–150. [12] J.M. Xu, A sufficient condition for equality of arc-connectivity and minimum degree of a digraph, Discrete Math. 133 (1994) 315–318.