Sufficient conditions for maximally restricted edge connected graphs

Sufficient conditions for maximally restricted edge connected graphs

Discrete Mathematics 312 (2012) 2969–2972 Contents lists available at SciVerse ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com...

189KB Sizes 0 Downloads 8 Views

Discrete Mathematics 312 (2012) 2969–2972

Contents lists available at SciVerse ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

Note

Sufficient conditions for maximally restricted edge connected graphs✩ Yingying Qin ∗ , Jianping Ou Department of Mathematics, Wuyi University, Jiangmen 529020, China

article

info

Article history: Received 5 November 2010 Received in revised form 25 March 2012 Accepted 11 May 2012 Available online 30 May 2012

abstract It is shown in this work that if graph G has degree sequence d1 ≥ d2 ≥ · · · ≥ dn ≥ 2 with l ′ i=1 (di + dn−i−1 ) > l(n + 2) holding for every 1 ≤ l ≤ n/2 − 2, then it is λ -optimal. The lower bound on the degree-summation is exemplified sharp. This observation generalizes the corresponding results of Bollobás on maximal edge connectivity of graphs. © 2012 Elsevier B.V. All rights reserved.

Keywords: Restricted edge connectivity Degree sequence

1. Introduction All graphs appearing in this work are simple and connected. The restricted edge connectivity λ′ (G) of a graph G is the minimum cardinality over all its restricted edge cuts, where an edge cut S of G is restricted if G − S contains no isolated vertices. Let ξ (G) = min{d(x) + d(y) − 2 : xy is an edge of graph G} is the minimum edge degree of graph G where d(x) indicates the degree of vertex x. Then λ′ (G) ≤ ξ (G) holds whenever G is a connected graph of order at least four and is not isomorphic to any star K1,n [5]; graph G is called maximally restricted edge connected, or simply λ′ -optimal, if the equality holds. It is known that communication networks are usually locally more reliable if they have greater restricted edge connectivity [2,9], and so the optimization of restricted edge connectivity draws a lot of attention. For details, the readers can refer to [1,6,12,10,14,15] and a survey [7]. In [11], we show that a connected k-regular graph G of order at least four is λ′ optimal if k > |V (G)|/2. To weaken the minimum degree condition, the authors present degree-sum condition in [13] and some degree sequence conditions for triangle-free graphs and bipartite graphs in [8]. In [3], Bollobás presents a sufficient condition for a graph to be maximally edge connected, which says that if graph G has degree sequence d1 ≥ d2 ≥ · · · ≥ dn , l n ≥ 2 and i=1 (di + dn−i ) > ln −1 holds for every 1 ≤ l ≤ min{⌊n/2⌋− 1, δ(G)}, then λ(G) = δ(G). Theorem 6 of this work presents a similar condition for graphs to be maximally restricted edge connected, other conditions are also presented. For any two subsets X , Y of the vertex set V (G) of graph G or two of its subgraphs, let [X , Y ] denote the set of edges with one end in X and the other end in Y . For other symbols and terminology not specified herein, we follow that of [4]. 2. Maximal restricted edge connectivity In what follows, S = [U , W ] is a minimum restricted edge cut of graph G. Write |U | = k ≥ 2 and assume without loss of generality that |U | ≤ |W |. Let d¯S = λ′ /k and dS (x) be the number of edges in S that are incident with x.

✩ Supported by National Natural Science Foundation of China (Grant No. 10801091; 11126326).



Corresponding author. E-mail addresses: [email protected] (Y. Qin), [email protected] (J. Ou).

0012-365X/$ – see front matter © 2012 Elsevier B.V. All rights reserved. doi:10.1016/j.disc.2012.05.008

2970

Y. Qin, J. Ou / Discrete Mathematics 312 (2012) 2969–2972

Lemma 1. If connected graph G has order at least four and minimum degree δ(G) ≥ 2, then λ′ (G) ≤ 2(k − 2 + d¯S ) or λ′ (G) = ξ (G). Proof. Let V (U ) = {x1 , x2 , . . . , xk } and assume that dS (x1 ) ≤ dS (x2 ) ≤ · · · ≤ dS (xk ). If defining t = min{i : xi ∈ N (x1 )} − 1, k then dG (x1 ) = dS (x1 ) + dU (x1 ) ≤ dS (x1 ) + k − t. Since i=1 dS (xi ) = λ′ (G) and dS (x1 ) ≤ dS (x2 ) ≤ · · · ≤ dS (xk ), it follows ′ that dS (xi ) ≤ (λ (G) − (i − 1)dS (x1 ))/(k − (i − 1)) holds for all t + 1 ≤ i ≤ k. Hence,

ξ (G) ≤ dG (x1 xt +1 ) = dG (x1 ) + dG (xt +1 ) − 2 ≤ (dS (x1 ) + k − t ) + ((λ′ (G) − tdS (x1 ))/(k − t ) + k − 1) − 2

(1)

where 0 ≤ dS (x1 ) ≤ λ′ (G)/k and 1 ≤ t ≤ k − 1. Since δ(G) ≥ 2, it follows that either dS (x1 ) = 0 and t ≤ k − 2, or dS (x1 ) ≥ 1 and t ≤ k − 1. And so, the binary function f (dS (x1 ), t ) = (dS (x1 ) + k − t ) + ((λ′ (G) − tdS (x1 ))/(k − t ) + k − 1) − 2 arrives at its maximum value when either dS (x1 ) = 0 and t = k − 2, or dS (x1 ) = λ′ (G)/k and t = 1, or dS (x1 ) = 1 and t = k − 1. Firstly, if dS (x1 ) = λ′ (G)/k and t = 1 then λ′ (G) ≤ ξ (G) ≤ 2(k − 2 + d¯S ). Secondly, if dS (x1 ) = 0 and t = k − 2 then λ′ (G) ≤ ξ (G) ≤ k − 1 +λ′ (G)/2. So, λ′ (G) ≤ 2k − 2 and d¯S < 2. When 1 ≤ d¯S = λ′ (G)/k < 2, we have λ′ (G) ≤ 2(k − 2 + d¯S ); when 0 < d¯S < 1, λ′ (G) = kd¯S < k ≤ 2(k − 2 + d¯S ) + 1, we also have λ′ (G) ≤ 2(k − 2 + d¯S ). Finally, if dS (x1 ) = 1 and t = k − 1 then λ′ (G) ≤ ξ (G) ≤ (dS (x1 ) + k − t ) + ((λ′ (G) − tdS (x1 ))/(k − t ) + k − 1) − 2 ≤ λ′ (G), which implies λ′ (G) = ξ (G).  Corollary 2. Let G be a connected graph with order at least four and minimum degree δ(G) ≥ 2. If λ′ (G) ̸= ξ (G), then λ′ (G) ≤ 2k. Proof. Since λ′ (G) ̸= ξ (G), it follows from Lemma 1 that kd¯S = λ′ (G) ≤ 2(k − 2 + d¯S ), which implies that either k = 2, or d¯S ≤ 2 and λ′ (G) ≤ 2k. Since λ′ (G) = ξ (G) when k = 2, the corollary follows.  Lemma 3. If connected graph G with order at least four has δ(G) ≥ 2 and λ′ (G) = 2k − i, then ξ (G) = 2k − i, where i = 0, 1, 2. Proof. Since λ′ (G) ≤ ξ (G), it suffices to show that ξ (G) ≤ λ′ (G). As is pointed out in the proof of Lemma 1, we need only to consider the following two cases: (1) dS (x1 ) = λ′ (G)/k and t = 1; (2) dS (x1 ) = 0 and t = k − 2. If dS (x1 ) = 0 and t = k − 2, then for any i ∈ {0, 1, 2} we have

ξ (G) ≤ d(x1 xk−1 ) = dG (x1 ) + dG (xk−1 ) − 2 ≤ 2 + (k − 1 + λ′ (G)/2) − 2 = 2k − 1 − i/2 ≤ 2k − i. Continue to consider the case when dS (x1 ) = λ′ (G)/k and t = 1. If i = 0, then dS (x1 ) = dS (x2 ) = 2. And so

ξ (G) ≤ dG (x1 x2 ) = dG (x1 ) + dG (x2 ) − 2 = dU (x1 ) + dS (x1 ) + dU (x2 ) + dS (x2 ) − 2 ≤ 2k. If i = 1, then dS (x1 ) = 1 and 1 ≤ dS (x2 ) ≤ 2. Hence, ξ (G) ≤ dG (x1 x2 ) ≤ 2k − 1. Finally, if i = 2 then dS (x1 ) + dS (x2 ) ≤ 2. We also have ξ (G) ≤ dG (x1 x2 ) ≤ 2k − 2. And so the lemma follows.  Remark 1. For any connected graph G with order at least four and δ(G) ≥ 2, we deduce that if k = 2, or k ≥ 3 and λ′ = 2k − i for some nonnegative integer i ≤ 2, then λ′ (G) = ξ (G). But if k ≥ 3 and λ′ (G) = 2k − i for any integer i ≥ 3, then the following examples show that there are graphs with λ′ (G) = 2k − i < ξ (G). Example 1. For the case when i ≥ 3, let graph G be obtained by adding an edge set S of size 2k − i to join two complete graphs Kk and Km such that Kk contains vertices x1 , x2 , . . . , xi with dS (x1 ) = dS (x2 ) = · · · = dS (xi ) = 1 in G and dS (x) = 2 for any vertex x of Kk − {x1 , x2 , . . . , xi }, where i ≤ k < m. Since x1 x2 has minimum edge degree ξ (G) = dG (x1 x2 ) = 2(k − 2) + dS (x1 ) + dS (x2 ) = 2k − 2, it follows that λ′ (G) = 2k − i < 2k − 2 = ξ (G). Example 2. For the case when i ≥ 5, let G be any graph obtained by adding an edge set S of size 2k − i to join two complete graphs Kk and Km , where k ≤ m. Since ξ (G) ≥ 2k − 4, it follows that λ′ (G) ≤ 2k − 5 < 2k − 4 ≤ ξ (G). From the discussion above, we deduce that if graph G is such that δ(G) ≥ 2 and 2k ≥ λ′ (G) ≥ 2k − 2, then G is maximally restricted edge connected. These observations are useful for proving the following results. Lemma 4. Let G be a connected graph with δ(G) ≥ 2 and order n ≥ 4. If ξ (G) ≥ n − 1, then λ′ (G) = ξ (G). Proof. Since δ(G) ≥ 2, it follows that G is not any star. And so, it contains restricted edge cuts. Suppose on the contrary that λ′ (G) < ξ (G). Then λ′ (G) ≤ 2k − 3 by Corollary 2 and Lemma 3. In what follows we shall get the contradiction ξ (G) ≤ 2k − 2 ≤ n − 2, and the lemma follows from it.

Y. Qin, J. Ou / Discrete Mathematics 312 (2012) 2969–2972

2971

Similar to the proof of Lemma 3, we need only to consider the following two cases: (1) dS (x1 ) = λ′ (G)/k and t = 1; (2) dS (x1 ) = 0 and t = k − 2. If dS (x1 ) = 0 and t = k − 2, then

ξ (G) ≤ d(x1 xk−1 ) = dG (x1 ) + dG (xk−1 ) − 2 ≤ 2 + (k − 1 + λ′ (G)/2) − 2 ≤ k − 1 + (2k − 3)/2 < 2k − 2. If dS (x1 ) = λ′ (G)/k and t = 1, since λ′ (G) ≤ 2k − 3, we deduce that dS (x1 ) + dS (x2 ) ≤ 2. And so,

ξ (G) ≤ dG (x1 x2 ) = dG (x1 ) + dG (x2 ) − 2 = dU (x1 ) + dS (x1 ) + dU (x2 ) + dS (x2 ) − 2 ≤ 2k − 2. The lemma follows.



Lemma 5. Let G be a connected graph with order at least four has δ(G) ≥ 2. If λ′ (G) < ξ (G), then 2λ′ (G) − dS (x1 ) − dS (x2 ) ≤ 4k − 8. Proof. Since λ′ (G) < ξ (G), it follows from Lemma 3 that λ′ (G) ≤ 2k − 3. If λ′ (G) ≤ 2k − 4, then 2λ′ (G) − dS (x1 ) − dS (x2 ) ≤ 4k − 8. Suppose on the contrary that 2λ′ (G) − dS (x1 ) − dS (x2 ) ≥ 4k − 7 when λ′ (G) = 2k − 3, then dS (x1 ) + dS (x2 ) ≤ 1 and dS (x1 ) = 0. If x2 ∈ N (x1 ), 2k − 3 ≥ dG (x1 x2 ) ≥ ξ (G) > λ′ (G) = 2k − 3, which is a contradiction. If x2 ̸∈ N (x1 ), denote t = |N (x1 )|. Since δ(G) ≥ 2 then 2 ≤ t ≤ k − 2, and k ≥ 4. Let xi ∈ N (x1 ) be a vertex that has the minimum degree in G among those in N (x1 ). Then dG (x1 xi ) = dG (x1 ) + dU (xi ) + dS (xi ) − 2

≤ t + k − 1 + (2k − 3)/t − 2 ≤ 2k − 3 + 1/(k − 2). Since 2k − 3 = λ′ (G) < ξ (G) ≤ dG (x1 xi ) ≤ 2k − 3, which is a contradiction.



Theorem 6. Let G be a graph with order n that contains restricted edge cuts and d1 ≥ d2 ≥ · · · ≥ dn ≥ 2 be its degree sequence. l ′ If i=1 (di + dn−i−1 ) > l(n + 2) holds for every 1 ≤ l ≤ n/2 − 2, then λ (G) = ξ (G). Proof. Suppose on the contrary that λ′ (G) < ξ (G). Then k ≥ 3. Let H be the graph obtained by adding as few as possible edges to G such that both U and W induce complete subgraphs in H, respectively. From Corollary 2 and Lemma 3 it follows that λ′ (G) = |[U , W ]| = λ′ (H ) = 2k − i with i ≥ 3. Let U ′ = U − {x1 , x2 }. Then k−2    (dn−i−1 + di ) ≤ dH (x) + max dH (y), x∈U ′

i=1

W′

y∈W ′

where W ′ ⊆ W contains (k − 2) vertices that have as large as possible degree in H. Then



dH (x) + max

x∈U ′

W′



dH (y) ≤ (k − 2)(k − 1) + λ′ (G) − dS (x1 ) − dS (x2 ) + (k − 2)(n − k − 1) + λ′ (G)

y∈W ′

= (k − 2)(k − 1) + (k − 2)(n − k − 1) + 2λ′ (G) − dS (x1 ) − dS (x2 ). k−2 By Lemma 5, we deduce that i=1 (dn−i−1 + di ) ≤ (k − 2)(n + 2). This contradiction establishes the theorem.



Corollary 7. Let G be a graph that contains restricted edge cuts and d1 ≥ d2 ≥ · · · ≥ dn ≥ 2 be its degree sequence. If di + dn−i−1 > n + 2 for every 1 ≤ i ≤ n/2, then λ′ (G) = ξ (G).  Remark 2. The bound on the degree-summation of Theorem 6 is sharp to some extent. A counterexample graph G can be constructed as follows. Let Kk and Kk+2 be two complete graphs with vertex-sets V (Kk ) = {x1 , x2 , . . . , xk } and V (Kk+2 ) = {y1 , y2 , . . . , yk+2 }. Add an edge set S of cardinality 2k − 3 to join the vertices of Kk and Kk+2 in such a way that the neighborhood of vertex xi in G is N (xi ) = {y1 } for i = 1, 2, 3; N (xi ) = {yi , yi+1 } for i = 4, 5, . . . , k − 1 and N (xk ) = {yk , y4 }. Clearly, graph G has degree sequence k, k, k, k + 1, k + 1, . . . , k + 1, k + 3, . . . , k + 3, k + 4, where the number of integers l k + 1 is k + 1 and the number of integers k + 3 is k − 3. And so, i=1 (dn−i−1 + di ) = l(2k + 4) = l(n + 2) for any integer l with 1 ≤ l ≤ k − 2. But, ξ (G) = 2k − 2 > 2k − 3 = |S | ≥ λ′ (G). Acknowledgments The authors are grateful to the Editor-in-chief and the anonymous referees for their very detailed comments, which greatly improved this paper.

2972

Y. Qin, J. Ou / Discrete Mathematics 312 (2012) 2969–2972

References [1] C. Balbuena, P. García-Vázquez, X. Marcote, Sufficient conditions for λ′ -optimality in graphs with girth g, J. Graph Theory 52 (2006) 73–86. [2] D. Bauer, F. Boesch, C. Suffel, et al., Combinatorial optimization problems in the analysis and design of probabilistic networks, Networks 15 (1989) 257–271. [3] B. Bollobás, On graphs with equal edge connectivity and minimum degree, Discrete Math. 28 (1979) 321–323. [4] J.A. Bondy, U.S.R. Murty, Graph Theory With Applications, Macmillan, London, 1976. [5] A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. [6] J. Fàbrega, M.A. Fiol, Extraconnectivity of graphs with large girth, Discrete Math. 127 (1994) 163–170. [7] A. Hellwig, L. Volkmann, Maximally edge-connected and vertex-connected graphs and digraphs: a survey, Discrete Math. 308 (2008) 3265–3296. [8] A. Hellwig, L. Volkmann, Sufficient conditions for graphs to be λ′ -optimal, super-edge connected and maximally edge connected, J. Graph Theory 48 (2005) 228–246. [9] L.Q. Li, Q. Li, Reliability analysis of circulant graphs, Networks 28 (1998) 61–65. [10] J.P. Ou, Edge cuts leaving components of order at least m, Discrete Math. 305 (2006) 365–371. [11] J.P. Ou, Restricted edge connectivity of regular graphs, J. Math. Study 34 (2001) 345–350. [12] J.P. Ou, F.J. Zhang, Super restricted edge connectivity of regular graphs, Graphs Combin. 21 (2005) 459–467. [13] L. Shang, H.P. Zhang, Sufficient conditions for graphs to be λ′ -optimal and super-λ′ , Networks 49 (2007) 234–242. [14] N. Ueffing, L. Volkmann, Restricted edge connectivity and minimum edge-degree, Ars Combin. 66 (2003) 193–203. [15] J.M. Xu, Restricted edge connectivity of vertex transitive graphs, Chin. Ann. Math. Ser. A 21 (2000) 605–608.