Degree Sequence Conditions for Maximally Edge-Connected Graphs and Digraphs Peter Dankelmann1 and Lutz Volkmann2 1 DEPARTMENT OF MATHEMATICS AND APPLIED MATHEMATICS UNIVERSITY OF NATAL DURBAN, SOUTH AFRICA E-mail: dankelma@scfs1.und.ac.za 2 LEHRSTUHL II FÜR MATHEMATIK RWTH AACHEN AACHEN, GERMANY E-mail: volkm@math2.rwth-aachen.de Received June 6, 1996 Abstract: In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue c 1997 John Wiley & Sons, Inc. J Graph Theory 26: 27–34, 1997 conditions for bipartite (di-)graphs. Keywords: graph, edge-connectivity, degree sequence Sufficient conditions for the equality of the edge-connectivity and the minimum degree of a graph were given by several authors. A classical result is the following condition for maximally edge-connected graphs due to Chartrand [2]. Here and in the sequel a (di-)graph has no loops or multiple edges. c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/010027-08 28 JOURNAL OF GRAPH THEORY Theorem 1 [2]. If Let G be a graph of order n with minimum degree δ and edge-connectivity λ. δ≥ then λ = δ. jnk 2 , Theorem 1 was the starting point for many other sufficient conditions for λ = δ. Lesniak [9] weakened the condition δ ≥ bn/2c to deg(u) + deg(v) ≥ n for all pairs of nonadjacent vertices u and v in G. Plesník [10] showed that every graph of diameter 2 satisfies λ = δ and thus generalized Lesniak's result. Improvements of Plesník's result can be found by Plesník, Znám [11] and Dankelmann, Volkmann [3] (see also the textbook of Volkmann [11, p. 318ff]). Goldsmith and White [8] proved that it is sufficient to have bn/2c disjoint pairs of vertices ui , vi with deg(ui ) + deg(vi ) ≥ n. Xu gave an analogue for directed graphs, which also includes the result by Goldsmith and White. Further conditions for λ = δ, depending on parameters not directly related to the vertex degrees, (e.g. girth and diameter) are given in [6, 4, 5, 12]. The following degree sequence condition of Bollobás [1] includes the condition of Goldsmith and White for odd n. Theorem 2 [1]. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and edge-connectivity λ. Suppose that for every l, 1 ≤ l ≤ min{n/2 − 1, δ} we have l X (di + dn−i ) ≥ ln − 1, i=1 then λ = δ. In this paper we give a degree sequence condition for directed graphs, which generalizes the result by Xu, while having a much simpler proof, and implies a stronger version of Theorem 2 for undirected graphs as well. Let D = (V, A) be a digraph with vertex set V = V (D) and arc set A = A(D). For a vertex v ∈ V the degree of v, denoted by deg(v) is defined as the minimum value of its out-degree deg + (v) and its in-degree deg − (v). The degree sequence of D is defined as the nonincreasing sequence of the degrees of the vertices of D. For two sets X, Y ⊂ V (D) we denote the set of arcs joining the vertices in X to the vertices in Y by (X, Y ). Theorem 3. Let D be a digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and arc-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and k X (di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 1 i=1 for some k with 1 ≤ k ≤ δ, then λ = δ. Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| < δ. We first show that the sets X and Y contain at least δ +1 vertices, and therefore δ ≤ bn/2c−1. Suppose X contains at most δ vertices. Then we obtain the contradiction X deg + (x) ≤ |X|(|X| − 1) + |(X, Y )| ≤ δ(|X| − 1) + |(X, Y )|. |X|δ ≤ x∈X DEGREE SEQUENCE CONDITIONS 29 Similarly one can show that |Y | ≥ δ + 1. Now let S ⊂ X and T ⊂ Y be two k-sets with 1 ≤ k ≤ δ. Since every vertex in X has at most |X| − 1 out-neighbors in X and there are at most δ − 1 arcs from X to Y , we have X deg + (v) ≤ k(|X| − 1) + δ − 1. v∈S Similarly, we have X deg − (v) ≤ k(|Y | − 1) + δ − 1, v∈T and thus, in total X deg(v) ≤ k(n − 2) + 2δ − 2. (1) v∈S∪T Now choose S (T ) to contain the k vertices in X (Y ) of highest degree. Then S ∪ T contains the k vertices of highest degree but not the δ + 1 − k vertices of lowest degree in D. Hence X deg(v) ≥ v∈S∪T k X (di + dn+i−δ−1 ), i=1 which yields together with (1) a contradiction to the hypothesis. Theorem 3 implies the following degree sequence condition by Xu [16]. Corollary 1[16]. Let D be a digraph of order n, arc-connectivity λ and minimum degree δ. If there are bn/2c disjoint pairs of vertices (vi , wi ) with deg(vi ) + deg(wi ) ≥ n for all i = 1, 2, . . . , bn/2c, then λ = δ. Proof. If δ ≥ bn/2c, then λ = δ by Theorem 3. If δ ≤ bn/2c − 1, then from the bn/2c pairs of vertices choose δ pairs (v10 , w10 ), (v20 , w20 ), . . . , (vδ0 , wδ0 ) containing the δ vertices of lowest degree of vi and wi . Then we have δ X (di + dn+i−δ−1 ) ≥ i=1 δ X deg(vi0 ) + deg(wi0 ) i=1 ≥ δn > δ(n − 2) + 2δ − 1. Now Theorem 3 with k = δ yields λ = δ. Remark. The proof of Corollary 1 shows that one can relax the condition on the degrees slightly by allowing one pair of vertices to have degree sum n − 1. Corollary 2. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and edge-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and k X (di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 1 i=1 for some k with 1 ≤ k ≤ δ, then λ = δ. 30 JOURNAL OF GRAPH THEORY Proof. Given the graph G, define the digraph D on the vertex set V (G) by replacing each edge of G by two arcs in opposite directions and apply Theorem 3 to D. Remark. Corollary 2 implies Theorem 1 as well as Theorem 2. P Remark. The following example shows that Corollary 2 is best possible in the sense that (di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 2 for some k ≤ δ does not guarantee λ = δ. Let H1 and H2 be two copies of the complete graph Kp with p ≥ 3, V (H1 ) = {x1 , . . . , xp }, and V (H2 ) = {y1 , . . . , yp }. We define the graph Gp as the union of H1 and H2 together with the new edges x1 y1 , x1 y2 , . . . , x1 yp−2 . Then n(Gp ) = n = 2p, δ(Gp ) = δ = p − 1 = n/2 − 1, λ(Gp ) = λ = p − 2, and δ X (di + dn+i−δ−1 ) = 2p(p − 1) − 2 = δ(n − 2) + 2δ − 2 i=1 In the case of a bipartite graph G, the sufficient conditions for λ = δ can be relaxed considerably. Volkmann [13], [14] proved that for a bipartite graph G instead of δ ≥ (n − 1)/2 only δ ≥ (n + 1)/4 is needed. In contrast to non-bipartite graphs, even a neighborhood condition is sufficient for maximally connected bipartite graphs. Dankelmann and Volkmann [3] showed that if for every pair (u, v) of vertices of distance two |N (u) ∪ N (v)| ≥ (n + 1)/4, then λ = δ. In the sequel let D = (V, A) denote a bipartite digraph with bipartition V = (V 0 , V 00 ). We adopt the convention that for every subset X of V (D), we denote the set X ∩ V 0 by X 0 and X ∩ V 00 by X 00 . The following degree sequence condition is an analogue to Theorem 3 for bipartite digraphs. Theorem 4. Let D be a bipartite digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or δ ≤ bn/4c and k X (di + dn+1−2δ+k−i ) ≥ k(n − 2δ) + 2δ − 1 i=1 for some k with 1 ≤ k ≤ 2δ, then λ = δ. Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| < δ. We first show that the sets X 0 , X 00 , Y 0 and Y 00 contain at least δ vertices, and therefore δ ≤ bn/4c. As shown in the proof of Theorem 3, |X| ≥ δ + 1. Hence, there exists a vertex u ∈ X with N + (u) ⊆ X. If without loss of generality u ∈ X 0 , then it follows |X 00 | ≥ δ. Now there exists a vertex v ∈ X 00 with N + (v) ⊆ X, and hence |X 0 | ≥ δ. Similarly one can show that |Y 0 |, |Y 00 | ≥ δ. Now let S ⊆ X and T ⊆ Y be two k-sets with 1 ≤ k ≤ 2δ. Every vertex in X 0 has at most |X 00 | ≤ |X| − δ out-neighbors in X. The same holds true for the vertices in X 00 . Since there are at most δ − 1 arcs from X to Y , we have X deg + (v) ≤ k(|X| − δ) + δ − 1. v∈S Similarly, we have X v∈T deg − (v) ≤ k(|Y | − δ) + δ − 1, DEGREE SEQUENCE CONDITIONS 31 and thus, in total X deg(v) ≤ k(n − 2δ) + 2δ − 2. (2) v∈S∪T Now choose S (T ) to contain the k vertices in X (Y ) of highest degree in D. Then S ∪ T contains the k vertices of highest degree in G but not the 2δ − k vertices of lowest degree. Hence X deg(v) ≥ k X (di + dn+1−2δ+k−i ), i=1 v∈S∪T which yields, together with (2), a contradiction to the hypothesis. As above, we obtain the following corollary for undirected bipartite graphs. Corollary 3. Let G be a bipartite graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and edge-connectivity λ. If δ ≥ b(n + 1)/4c or if δ ≤ bn/4c and k X (di + dn+1−2δ+k−i ) ≥ k(n − 2δ) + 2δ − 1 i=1 for some k with 1 ≤ k ≤ 2δ, then λ = δ. P Remark. The following example shows that Corollary 3 is best possible in the sense that (di + dn+1−2δ+k−i ) ≥ k(n + 2δ) + 2δ − 2 for some k ≤ 2δ does not guarantee λ = δ. Let H1 and H2 be two copies of the complete bipartite graph Kp,p with p ≥ 1, V (H1 ) = {x01 , . . . , x0p } ∪ {x001 , . . . , x00p } and V (H2 ) = {y10 , . . . , yp0 } ∪ {y100 , . . . , yp00 }. We define the graph Gp,p as the 00 union of H1 and H2 together with the new edges x01 y100 , . . . , x0p−1 yp−1 . Then n(Gp,p ) = n = 4p, δ(Gp,p ) = δ = p = n/4, λ(Gp,p ) = λ = p − 1, and 2δ X (di + dn+1−i ) = 4p · 2p + 2(p − 1) = 2δ(n − 2δ) + 2δ − 2. i=1 The following variation of Theorem 4 can be proved by choosing four sets S 0 , S 00 , T 0 , T 00 to contain the k vertices of highest degree in X 0 , X 00 , Y 0 , Y 00 , respectively, and using estimates of the form X deg + (v) ≤ k|X| + δ − 1, v∈S 0 ∪S 00 X deg − (v) ≤ k|Y | + δ − 1. v∈T 0 ∪T 00 As above, the graph Gp,p shows the sharpness of the Theorem. Theorem 5. Let D be a bipartite digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or if δ ≤ bn/4c and k X i=1 di + 3k X i=1 for some k with 1 ≤ k ≤ δ, then λ = δ. dn+1−δ+k−i ≥ kn + 2δ − 1 32 JOURNAL OF GRAPH THEORY We conclude the paper with degree conditions that consider only the lower end of the degree sequence. Theorem 6. Let D be a digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and arc-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and 2k X dn+1−i ≥ kn − 3 i=1 for some k with 2 ≤ k ≤ δ, then λ = δ. Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| < δ. As shown in Theorem 3, |X|, |Y | ≥ δ + 1 and δ ≤ bn/2c − 1. Now let S ⊂ X and T ⊂ Y be two k-sets with 2 ≤ k ≤ δ. If we choose S such that the number of arcs of (X, Y ) incident with S is minimal, then we conclude X deg + (v) ≤ k(|X| − 1) + (δ − 1) − (δ + 1 − k) = k|X| − 2. v∈S Similarly, we have X deg − (v) ≤ k|Y | − 2, v∈T and thus, in total 2k X dn+1−i ≤ i=1 X deg(v) ≤ kn − 4, v∈S∪T which yields a contradiction to the hypothesis. Corollary 4. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and edge-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and 2k X dn+1−i ≥ kn − 3 i=1 for some k with 2 ≤ k ≤ δ, then λ = δ. Remark. The following example shows that Corollary 4 is best possible in the sense that P dn+1−i ≥ kn − 4 for some k ≤ δ does not guarantee λ = δ. Let H1 and H2 be two copies of the complete graph Kp with p ≥ 3, V (H1 ) = {x1 , . . . , xp }, and V (H2 ) = {y1 , . . . , yp }. We define the graph Gp as the union of H1 and H2 together with the new edges x1 y1 , . . . , xp−2 yp−2 . Then n(Gp ) = n = 2p, δ(Gp ) = δ = p − 1 = n/2 − 1, λ(Gp ) = λ = p − 2, and 2δ X dn+1−i = (2p − 2)p − 4 = δn − 4. i=1 Again there is an analogue to Theorem 6 for bipartite (di)graphs. DEGREE SEQUENCE CONDITIONS 33 Theorem 7. Let D be a bipartite (di)graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or δ ≤ bn/4c and 4k X dn+1−i ≥ k(n + 2) − 1 i=1 for some k with 1 ≤ k ≤ δ, then λ = δ. Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D) with X ∪ Y = V (D) and |(X, Y )| < δ. As shown in Theorem 4, |X 0 |, |X 00 |, |Y 0 |, |Y 00 | ≥ δ and δ ≤ n/4. Now let S 0 ⊆ X 0 , S 00 ⊆ X 00 , T 0 ⊆ Y 0 , and T 00 ⊆ Y 00 be four k-sets with 1 ≤ k ≤ δ, such that the number of arcs of (X, Y ) incident with S 0 ∪ S 00 is minimal. It is easy to verify that this number is maximal if no vertex in X is incident with more than one arc of (X, Y ) and if all the vertices of X adjacent to vertices in Y are in the same partition set. Since X 0 and X 00 contain at least δ vertices each, we have |(S 0 ∪ S 00 , Y )| ≤ k − 1 and thus X deg + (v) ≤ k|X 00 | + k|X 0 | + k − 1. v∈S 0 ∪S 00 Similarly we have X deg − (v) ≤ k|Y 00 | + k|Y 0 | + k − 1. v∈T 0 ∪T 00 and thus, in total 4k X i=1 dn+1−i ≤ X deg(v) ≤ k(n + 2) − 2, v∈S∪T which yields a contradiction to the hypothesis. Remark. As above, the graph Gp,p shows that guarantee λ = δ. P dn+1−i ≥ k(n + 2) − 2 for some k does not References [1] B. Bollobás, On graphs with equal edge-connectivity and minimum degree, Discrete Math. 28 (1979), 321–323. [2] G. Chartrand, A graph theoretic approach to a communications problem, SIAM J. Appl. Math. 14 (1966), 778–781. [3] P. Dankelmann and L. Volkmann, New sufficient conditions for equality of minimum degree and edge-connectivity, Ars Combin. 40 (1995), 270–278. [4] J. Fabrega and M. A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (1989), 657–668. [5] J. Fabrega and M. A. Fiol, Bipartite graphs and digraphs with maximum connectivity, Discrete Appl. Math. 69 (1996), 271–279. [6] M. A. Fiol, The connectivity of large digraphs and graphs, J. Graph Theory 17 (1993), 31–45. [7] D. L. Goldsmith and R. C. Entringer, A sufficient condition for equality of edge-connectivity and minimum degree of a graph, J. Graph Theory. 3 (1979), 251–255. [8] D. L. Goldsmith and A. T. White, On graphs with equal edge-connectivity and minimum degree, Discrete Math. 23 (1978), 31–36. 34 JOURNAL OF GRAPH THEORY [9] L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math. 8 (1974), 351–354. [10] J. Plesník, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Commenian Math. 30 (1975), 71–93. [11] J. Plesník and S. Znám, On equality of edge-connectivity and minimum degree of a graph, Arch. Math. (Brno) 25 (1989), 19–25. [12] T. Soneoka, H. Nakada, and M. Imase, Sufficient conditions for maximally connected dense graphs, Discrete Math. 63 (1987), 53–66. [13] L. Volkmann, Bemerkungen zum p-fachen Kantenzusammenhang von Graphen, An. Univ. Buccuresti Mat. 37 (1988), 75–79. [14] L. Volkmann, Edge-connectivity in p-partite graphs, J. Graph Theory 13 (1989), 1–6. [15] L. Volkmann, Fundamente der Graphentheorie, Springer-Verlag, Wien/New York (1996). [16] J.-M. Xu, A sufficient condition for equality of arc-connectivity and minimum degree of a digraph, Discrete Math. 133 (1994), 315–318.

1/--страниц