- Email: [email protected]

Contents lists available at ScienceDirect

Theoretical Computer Science www.elsevier.com/locate/tcs

Suﬃcient conditions for k-restricted edge connected graphs ✩ Shiying Wang a,b,∗ , Lei Zhang a a b

School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, PR China College of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China

a r t i c l e

i n f o

Article history: Received 14 February 2014 Received in revised form 16 July 2014 Accepted 28 August 2014 Available online 4 September 2014 Communicated by S.-y. Hsieh Keywords: Interconnection networks k-Restricted edge connectivity λk -Optimality Neighborhood

a b s t r a c t For a connected graph G = ( V , E ), an edge set S ⊆ E is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk (G ), is deﬁned as the cardinality of a minimum k-restricted edge cut. Let ξk (G ) = min{|[ X , X¯ ]| : | X | = k, G [ X ] is connected}, where X¯ = V \ X. G is maximally k-restricted edge connected (λk -optimal for short) if λk (G ) = ξk (G ). The k-restricted edge connectivity is more reﬁned network reliability indices than edge connectivity. In this paper, let k ≥ 2 be an integer, and let G be a graph of order ν (G ) at least 2k satisfying | N (u ) ∩ N ( v )| ≥ 2k − 2 for all pairs u , v of nonadjacent vertices. If for each triangle T there exists at least one vertex v ∈ V ( T ) such that d( v ) ≥ ν (2G ) + k − 1, then G is λk -optimal. © 2014 Elsevier B.V. All rights reserved.

1. Terminology and introduction For graph-theoretical terminology and notation not deﬁned here we follow [4]. We consider ﬁnite, undirected and simple graphs. Let G be a graph with vertex set V = V (G ) and edge set E = E (G ). The order (size) of G is the number of vertices (edges) in G, the order will be denoted by ν (G ). The set of neighbors of a vertex v in a graph G is denoted by N G ( v ). Denote by δ(G ) the minimum degree of G. If G is a subgraph of G and v is a vertex of G , we deﬁne N G ( v ) = N G ( v ) ∩ V (G ). Unambiguously, we use N ( v ) for N G ( v ), and use N [ v ] for N ( v ) ∪ { v }. For U ⊆ V (G ), let G [U ] be the subgraph induced by U , and let N (U ) = {u ∈ V (G ) : uv ∈ E (G ) and v ∈ U }. A path is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Likewise, a cycle on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. The length of a path or cycle is the number of its edges. A path or cycle of length k is called a k-path or k-cycle, respectively. Let G be a connected graph. If the ends of a path are u and v, then this path is called a (u , v )-path. The length of a shortest (x, y )-path of G is called the distance between x and y and denoted d G (x, y ). For subsets X and Y of V (G ), we denote by [ X , Y ] the set of edges with one end in X and the other in Y . An edge cut of G is a set of edges whose removal makes the remaining graph no longer connected. An interconnection network can be conveniently modeled as a graph G = ( V , E ). A classical measurement of the fault tolerance of a network is the edge connectivity λ(G ). In general, the larger the λ(G ) is, the more reliable the network is.

✩ This work is supported by the National Natural Science Foundation of China (61370001) and the Doctoral Fund of Ministry of Education of China (20111401110005). Corresponding author at: School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, PR China. E-mail addresses: [email protected], [email protected] (S. Wang), [email protected] (L. Zhang).

*

http://dx.doi.org/10.1016/j.tcs.2014.08.018 0304-3975/© 2014 Elsevier B.V. All rights reserved.

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

67

The edge connectivity λ(G ) of a graph G is the minimum cardinality of an edge cut of G. As a more reﬁned index than the edge connectivity, the restricted edge connectivity was proposed by Esfahanian and Hakimi in [11]. An edge set S ⊆ E (G ) is said to be a restricted edge cut if G − S is disconnected and every component of G − S contains at least 2 vertices. If such an edge cut exists, then the restricted edge connectivity of G, denoted by λ (G ), is deﬁned to be the minimum number of edges over all restricted edge cuts of G. A graph is called λ -connected if it contains restricted edge cuts. For e = uv ∈ E (G ), let ξG (e ) = d(u ) + d( v ) − 2 be the edge degree of e. In [5], the authors proved that each connected graph G of order ν = ν (G ) ≥ 4 except a star K 1,ν −1 is λ -connected and satisﬁes λ(G ) ≤ λ (G ) ≤ ξ(G ), where ξ(G ) = min{d G (u ) + d G ( v ) − 2 : uv ∈ E (G )} is the minimum edge degree of G. A graph G is λ -optimal if λ (G ) = ξ(G ). Suﬃcient conditions for graphs to be λ -optimal were given by several authors [1,2,5,18,19]. In [12], Fàbrega and Fiol proposed the more general concept of k-restricted edge connectivity. For a connected graph G, an edge set S ⊆ E (G ) is called a k-restricted edge cut of G if G − S is disconnected and every component of G − S has at least k vertices. A minimum k-restricted edge cut is called a λk -cut. The k-restricted edge connectivity of G, denoted by λk (G ), is deﬁned as the cardinality of a λk -cut. It should be pointed out that not all connected graphs have a k-restricted edge cut. A connected graph G is said to be λk -connected if G has a k-restricted edge cut. It is easy to see that if G is λk -connected for k ≥ 2, then G is also λk−1 -connected and λk−1 (G ) ≤ λk (G ). As an important index to estimate the reliability of networks, the k-restricted edge connectivity recently has received a lot of attention [8,9,11,13,14,17,20]. Let G 1 and G 2 be two graphs having the same order and size. In view of recent studies on k-restricted edge connectivity [6,10,18,22], it seems that the graph G 1 is more reliable than the graph G 2 if λi (G 1 ) = λi (G 2 ), i = 1, 2, . . . , k − 1, and λk (G 1 ) > λk (G 2 ). So, we expect λk (G ) to be as large as possible. The optimization of λk (G ) requires an upper bound ﬁrst. For any positive integer k, let ξk (G ) = min{|[ X , X¯ ]| : | X | = k, G [ X ] is connected}, where X¯ = V (G )\ X . It has been shown that λk (G ) ≤ ξk (G ) holds for many graphs (see [7,23,26,27]). A connected graph G is called a λk -optimal graph if λk (G ) = ξk (G ). Clearly, λ(G ) = λ1 (G ), λ (G ) = λ2 (G ), δ(G ) = ξ1 (G ) and ξ(G ) = ξ2 (G ). In recent years, there are a lot of studies on λk -optimal graphs for k = 2, 3 [3,15,21,24,25], while the studies for general k are relatively less. The general rules for general k need to be explored further. In [16], Hellwig and Volkmann gave the following suﬃcient condition for λ -optimality in graphs of diameter 2. Theorem 1.1. (See [16].) Let G be a λ -connected graph satisfying | N (u ) ∩ N ( v )| ≥ 2 for all pairs u , v of nonadjacent vertices. If for each triangle T there exists at least one vertex v ∈ V ( T ) such that d( v ) ≥ ν (2G ) + 1, then G is λ -optimal. In this paper, we give a suﬃcient condition for graphs to be λk -optimal, which extends Theorem 1.1 when k ≥ 2. Theorem 1.2. Let k ≥ 2 be an integer, and let G be a graph of order ν (G ) at least 2k satisfying | N (u ) ∩ N ( v )| ≥ 2k − 2 for all pairs u , v ν (G ) of nonadjacent vertices. If for each triangle T there exists at least one vertex v ∈ V ( T ) such that d( v ) ≥ 2 + k − 1, then G is λk -optimal. 2. Preliminaries Let G be a λk -connected graph, and let S be a λk -cut of G. It has been shown in [23] that there exists X ⊂ V (G ) such that G [ X ] and G [Y ] are both the connected induced subgraphs of orders at least k and S = [ X , Y ], where Y = X¯ = V (G )\ X . We deﬁne X k = {x ∈ X : | N (x) ∩ Y | ≥ k}, Y k = { y ∈ Y : | N ( y ) ∩ X | ≥ k}, X i = {x ∈ X : | N (x) ∩ Y | = i }, Y i = { y ∈ Y : | N ( y ) ∩ X | = i }, k−2 k−1 where i = 0, 1, 2, . . . , k − 1. Let X ≤k−2 = i =0 X i and Y ≤k−1 = i =0 Y i . In order to prove our main result, we ﬁrst give some useful lemmas. Lemma 2.1. (See [26].) Let k ≥ 2 be an integer and let G be a graph of order at least 2k. If each pair u , v of nonadjacent vertices satisﬁes | N (u ) ∩ N ( v )| ≥ k, then G is λk -connected and λk (G ) ≤ ξk (G ). Lemma 2.2. (See [23].) Let G be a λk -connected graph with λk (G ) ≤ ξk (G ) and let S = [ X , Y ] be a λk -cut of G. (i) If there exists a connected subgraph H of order k in G [ X ] with the property that

N ( v ) ∩ V ( H ) ≤

v ∈ X \V (H )

N ( v ) ∩ Y ,

v ∈ X \V (H )

then G is λk -optimal. (ii) There exists no connected subgraph H of order k in G [ X ] with the property that

N ( v ) ∩ V ( H ) <

v ∈ X \V (H )

N ( v ) ∩ Y .

v ∈ X \V (H )

Lemma 2.3. Let G be a λ3 -connected graph of order at least 6, and let S = [ X , Y ] be a λ3 -cut of G. If | N (u ) ∩ N ( v )| ≥ 4 for all pairs u , v of nonadjacent vertices and | X 2 | ≤ 2 or |Y 2 | ≤ 2, then G is λ3 -optimal.

68

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

Proof. By Lemma 2.1, λ3 (G ) ≤ ξ3 (G ). As S = [ X , Y ] is a λ3 -cut of G, G [ X ] and G [Y ] are connected. If | X | = 3 or |Y | = 3, then we are done. Now, let | X | ≥ 4 and |Y | ≥ 4. Without loss of generality, suppose that | X 2 | ≤ 2. Claim. X 0 = ∅. Suppose, on the contrary, that X 0 = ∅. Then there exists a vertex x ∈ X 0 such that | N (x) ∩ Y | = 0. For any y ∈ Y , we can deduce that

N ( y ) ∩ X ≥ N (x) ∩ N ( y ) ∩ X = N (x) ∩ N ( y ) − N (x) ∩ N ( y ) ∩ Y ≥ N (x) ∩ N ( y ) − N (x) ∩ Y ≥ 4. Since G [Y ] is connected, there exists a connected subgraph H of order 3 in G [Y ] with the property that

N ( v ) ∩ V ( H ) ≤

v ∈Y \ V ( H )

V ( H )

v ∈Y \ V ( H )

= 3Y \ V ( H ) < 4Y \ V ( H ) N ( v ) ∩ X . ≤ v ∈Y \ V ( H )

This contradicts to Lemma 2.2(ii). The proof of Claim is complete. Case 1. X 1 = ∅. By | X 2 | ≤ 2, we consider the following two cases. Case 1.1. | X 2 | ≤ 1. By Claim, we have X 0 = X 1 = ∅. Since G [ X ] is connected, there exists a connected subgraph H 1 of order 3 in G [ X ] such that X 2 ⊆ V ( H 1 ). Hence,

N ( v ) ∩ V ( H 1 ) ≤

v ∈ X \V (H 1 )

N ( v ) ∩ Y .

v ∈ X \V (H 1 )

By Lemma 2.2(i), G is λ3 -optimal. Case 1.2. | X 2 | = 2. Suppose X 2 = {x1 , x2 }. If there exists a connected subgraph H 2 of order 3 in G [ X ] such that X 2 ⊆ V ( H 2 ), then we have that

N ( v ) ∩ V ( H 2 ) ≤

v ∈ X \V (H 2 )

N ( v ) ∩ Y .

v ∈ X \V (H 2 )

By Lemma 2.2(i), G is λ3 -optimal. We assume that there exists no connected subgraph H of order 3 in G [ X ] such that X 2 ⊆ V ( H ). Since G [ X ] is connected, there exists a 2-path P in G [ X ] such that | V ( P ) ∩ X 2 | = 1 and d G [ X ] (x1 , x2 ) ≥ 3. It means that there exists a vertex u ∈ X 2 such that | N (u ) ∩ V ( P )| ≤ 1 < | N (u ) ∩ Y |, and | N ( v ) ∩ V ( P )| ≤ | N ( v ) ∩ Y | for any v ∈ X \( V ( P ) ∪ {u }). Therefore,

N (x) ∩ Y .

N (x) ∩ V ( P ) <

x∈ X \ V ( P )

x∈ X \ V ( P )

By Lemma 2.2(ii), a contradiction. Case 2. X 1 = ∅. Let x0 ∈ X 1 , { y 0 } = N (x0 ) ∩ Y . For any y ∈ Y \{ y 0 }, by assumption, we have that | N ( y ) ∩ X | ≥ | N ( y ) ∩ N (x0 ) ∩ X | = | N ( y ) ∩ N (x0 )| − | N ( y ) ∩ N (x0 ) ∩ Y | ≥ | N ( y ) ∩ N (x0 )| − | N (x0 ) ∩ Y | ≥ 4 − 1 = 3. Since G [Y ] is connected, there exists a subgraph H of order 3 in G [Y ] such that y 0 ∈ V ( H ). Hence, we can deduce that

N ( v ) ∩ V ( H ) ≤

v ∈Y \ V ( H )

N ( v ) ∩ X .

v ∈Y \ V ( H )

By Lemma 2.2(i), G is λ3 -optimal.

2

By Lemma 2.3, it is easy to verify that the following corollaries hold. Corollary 2.4. Let G be a λ3 -connected graph of order at least 6 satisfying | N (u ) ∩ N ( v )| ≥ 4 for all pairs u , v of nonadjacent vertices, and let S = [ X , Y ] be a λ3 -cut of G. If X ≤k−2 = ∅ or Y ≤k−1 \Y 2 = ∅, then G is λ3 -optimal.

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

69

Corollary 2.5. Let G be a λ3 -connected graph of order at least 6 satisfying | N (u ) ∩ N ( v )| ≥ 4 for all pairs u , v of nonadjacent vertices, and let S = [ X , Y ] be a λ3 -cut of G. G is λ3 -optimal if one of the following two conditions holds: (a) X ≤k−2 = ∅ and | X 2 | ≤ 2, (b) Y ≤k−1 \Y 2 = ∅ and |Y 2 | ≤ 2. 3. The proof of the main result Lemma 3.1. Let k ≥ 2 be an integer and let G be a λk -connected graph of order at least 2k, and let S = [ X , Y ] be a λk -cut of G such that | X | ≥ k + 1 and |Y | ≥ k + 1. If | N (u ) ∩ N ( v )| ≥ 2k − 2 for all pairs u , v of nonadjacent vertices, then there exists a (k − 1)-path in G [ X ] and G [Y ], respectively. Proof. By symmetry, it suﬃces to prove that there exists a (k − 1)-path in G [ X ]. Let P = x1 x2 . . . xl be a longest path in G [ X ]. If l ≥ k, then there exists a (k − 1)-path in P , and so we are done. Suppose, on the contrary, that l < k. Then x1 and every vertex in X \ V ( P ) are nonadjacent by the maximality of P , which implies N (x1 ) ∩ X = N (x1 ) ∩ V ( P ). Suppose that | N (x1 ) ∩ X | < | N (x1 ) ∩ Y |. Let S 1 = [ X \{x1 }, Y ∪ {x1 }]. Clearly, | S 1 | < | S |. Note that N (x1 ) ∩ X = ∅. Then N (x1 ) ∩ Y = ∅ and so Y ∪ {x1 } is connected. If G [ X \{x1 }] is not connected and C 1 , C 2 , . . . , C t are its components, then P − x1 must be in some component, say C 1 . Since G [ X ] is connected, there exists a vertex x∗ in C 2 such that x∗ is adjacent to x1 , a contradiction to N (x1 ) ∩ X = N (x1 ) ∩ V ( P ). Hence, X \{x1 } is also connected. Then, S 1 is a λk -cut, a contradiction. So, | N (x1 ) ∩ X | ≥ | N (x1 ) ∩ Y |. For any x ∈ V (G )\ N [x1 ], we have

2k − 2 ≤ N (x1 ) ∩ N (x)

≤ N (x1 ) = N (x1 ) ∩ X + N (x1 ) ∩ Y ≤ 2 N (x1 ) ∩ X = 2 N (x1 ) ∩ V ( P )

≤ 2(l − 1) < 2(k − 1) = 2k − 2, a contradiction.

2

Lemma 3.2. Let k ≥ 4 be an integer and let G be a λk -connected graph of order at least 2k satisfying | N (u ) ∩ N ( v )| ≥ 2k − 2 for all pairs u , v of nonadjacent vertices, and let S = [ X , Y ] be a λk -cut of G. If X ≤k−2 = ∅ or Y ≤k−1 \Y k−1 = ∅, then G is λk -optimal. Proof. By Lemma 2.1, λk (G ) ≤ ξk (G ). If | X | = k or |Y | = k, then we are done. Now, let | X | ≥ k + 1 and |Y | ≥ k + 1. Without loss of generality, it suﬃces to consider the case that min{| N (x) ∩ Y | : x ∈ X } ≤ min{| N ( y ) ∩ X | : y ∈ Y } and X ≤k−2 = ∅. Claim 1. X 0 = ∅. Suppose, on the contrary, that X 0 = ∅. Suppose x ∈ X 0 . By the hypotheses, for any y ∈ Y , we can deduce that | N ( y ) ∩ X | ≥ | N (x ) ∩ N ( y ) ∩ X | = | N (x ) ∩ N ( y )| − | N (x ) ∩ N ( y ) ∩ Y | ≥ | N (x ) ∩ N ( y )| − | N (x ) ∩ Y | ≥ 2k − 2 > k. Since G [Y ] is connected, there exists a connected subgraph H of order k in G [Y ] such that

N ( v ) ∩ V ( H ) <

v ∈Y \ V ( H )

N ( v ) ∩ X .

v ∈Y \ V ( H )

By Lemma 2.2(ii), a contradiction. The proof of Claim 1 is complete. If Y ≤k−1 = ∅, then | N ( v ) ∩ X | ≥ k for any v ∈ Y . Since G [Y ] is connected, there exists a connected subgraph H of order k such that

v ∈Y \ V ( H )

N ( v ) ∩ V ( H ) ≤

N ( v ) ∩ X .

v ∈Y \ V ( H )

By Lemma 2.2(i), G is λk -optimal. In the following, we consider Y ≤k−1 = ∅. By Claim 1, X 0 = ∅. Combining this with X ≤k−2 = ∅, there exists an integer 1 ≤ m ≤ k − 2 such that X i = ∅ for any

m−1

0 ≤ i < m and X m = ∅. It means that i =0 X i = ∅. By the assumption, X m ⊆ X ≤k−2 . We choose one vertex x0 ∈ X m ⊆ X ≤k−2 . By Lemma 3.1, there exists a (k − 1)-path P = y 1 y 2 . . . yk−1 yk in G [Y ] such that P contains as many vertices in N (x0 ) ∩ Y ≤k−1 as possible. Combining |Y | ≥ k + 1 with m ≤ k − 2, we have Y \ N (x0 ) = ∅. For any y ∈ Y \ N (x0 ), we can deduce that | N ( y ) ∩ X | ≥ | N (x0 ) ∩ N ( y ) ∩ X | = | N (x0 ) ∩ N ( y )| − | N (x0 ) ∩ N ( y ) ∩ Y | ≥ | N (x0 ) ∩ N ( y )| − | N (x0 ) ∩ Y | ≥ 2k − 2 − (k − 2) ≥ k. If there exists one vertex u ∈ Y ≤k−1 , which is nonadjacent to x for any x ∈ X ≤k−2 , then, by assumption, 2k − 2 ≤ | N (x) ∩ N (u )| = | N (x) ∩ N (u ) ∩ X | + | N (x) ∩ N (u ) ∩ Y | ≤ | N (u ) ∩ X | + | N (x) ∩ Y | ≤ (k − 1) + (k − 2) ≤ 2k − 3, a contradiction. Hence, Y ≤k−1 ⊆ N (x) for any x ∈ X ≤k−2 . Note that | N (u ) ∩ X | ≥ k for any u ∈ ( N (x0 ) ∩ Y )\Y ≤k−1 ⊆ Y \Y ≤k−1 . If N (x0 ) ∩ Y ≤k−1 ⊆ V ( P ), then

70

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

N ( v ) ∩ V ( P ) ≤

v ∈Y \ V ( P )

N ( v ) ∩ X .

v ∈Y \ V ( P )

By Lemma 2.2(i), G is λk -optimal. Suppose that ( N (x0 ) ∩ Y ≤k−1 )\ V ( P ) = ∅. Note that | N ( v ) ∩ V ( P )| ≤ k ≤ | N ( v ) ∩ X | for any v ∈ Y \( N (x0 ) ∪ V ( P )). If | N ( y ) ∩ V ( P )| ≤ | N ( y ) ∩ X | for any y ∈ ( N (x0 ) ∩ Y )\ V ( P ), then

v ∈Y \ V ( P )

N ( v ) ∩ V ( P ) ≤

N ( v ) ∩ X .

v ∈Y \ V ( P )

By Lemma 2.2(i), G is λk -optimal. Next, assume that there exists at least one vertex y 0 ∈ ( N (x0 ) ∩ Y )\ V ( P ) such that | N ( y 0 ) ∩ X | < | N ( y 0 ) ∩ V ( P )| ≤ k. Clearly, y 0 ∈ N (x0 ) ∩ Y ≤k−1 . 1 Case 1. | N ( y 0 ) ∩ V ( P )| ≤ k+ . 2

Since min{| N (x) ∩ Y | : x ∈ X } ≤ min{| N ( y ) ∩ X | : y ∈ Y } and is nonadjacent to y 0 for any y ∈ Y , then

m−1 i =0

1 X i = ∅, we have that m ≤ | N ( y 0 ) ∩ X | ≤ k+ − 1. If y 2

N ( y ) ∩ N ( y 0 ) ∩ Y \ V ( P ) = N ( y ) ∩ N ( y 0 ) ∩ Y − N ( y ) ∩ N ( y 0 ) ∩ V ( P ) = N ( y ) ∩ N ( y 0 ) − N ( y ) ∩ N ( y 0 ) ∩ X − N ( y ) ∩ N ( y 0 ) ∩ V ( P ) ≥ N ( y ) ∩ N ( y 0 ) − N ( y 0 ) ∩ X − N ( y 0 ) ∩ V ( P ).

1 Note that | N ( y 0 ) ∩ X | < | N ( y 0 ) ∩ V ( P )| ≤ k+ . By (1) and k ≥ 4, |( N ( y ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ 2k − 2 −( k+2 1 − 1) − k+2 1 ≥ 2

1 k − 2 ≥ 2. Recalling that ( N (x0 ) ∩ Y )\ V ( P ) = ∅ and x0 ∈ X m , we have | N (x0 ) ∩ V ( P )| ≤ m − 1 < k+ − 1. 2 Claim 2. y 1 , yk ∈ N (x0 ) ∩ Y ≤k−1 . Suppose that y 1 , yk ∈ / N (x0 ) ∩ Y ≤k−1 . If y 0 is adjacent to y 2 , then P 1 = y 0 y 2 . . . yk is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 1 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . If y 0 is nonadjacent to y 2 , then, by (1), |( N ( y 2 ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ | N ( y 2 ) ∩ N ( y 0 )| − | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2. Hence, there exists u 1 ∈ ( N ( y 0 ) ∩ N ( y 2 ) ∩ Y )\ V ( P ). We can deduce that P 2 = y 0 u 1 y 2 . . . yk−1 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 2 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, y 1 ∈ N (x0 ) ∩ Y ≤k−1 or yk ∈ N (x0 ) ∩ Y ≤k−1 , say y 1 ∈ N (x0 ) ∩ Y ≤k−1 . Suppose that yk ∈ / N (x0 ) ∩ Y ≤k−1 . If y 0 is adjacent to y 1 , then P 3 = y 0 y 1 . . . yk−1 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 3 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, y 0 is nonadjacent to y 1 . Similarly, y 0 is nonadjacent to yk−1 . By (1), |( N ( y 1 ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ | N ( y 1 ) ∩ N ( y 0 )| − | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2, and so there exists one vertex u 2 ∈ ( N ( y 0 ) ∩ N ( y 1 ) ∩ Y )\ V ( P ). If yk−1 ∈ / N (x0 ) ∩ Y ≤k−1 , then P 4 = y 0 u 2 y 1 . . . yk−2 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 4 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, yk−1 ∈ N (x0 ) ∩ Y ≤k−1 .

| V ( P )\{ y }|

1 k Note that | N (x0 ) ∩ V ( P )| ≤ k+ − 2. Since − | N (x0 ) ∩ V ( P )| ≥ k−2 1 − ( k+2 1 − 2) ≥ 1, there exists a subpath 2 2 P = y i . . . y j of length at least 3 in P − yk such that exactly two end vertices of P are adjacent to x0 . Note that y 0 is nonadjacent to yk−1 . By (1), |( N ( yk−1 ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ | N ( yk−1 ) ∩ N ( y 0 )| − | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2, and so there exists one vertex u 3 ∈ ( N ( y 0 ) ∩ N ( yk−1 ) ∩ Y )\ V ( P ), where u 3 = u 2 . Let P 5 = y i +3 . . . yk−1 u 3 y 0 u 2 y 1 . . . y i (see Fig. 1(a)). Then P 5 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 5 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . The proof of Claim 2 is complete. 1 Recalling that | N (x0 ) ∩ V ( P )| ≤ k+ − 2, we have | V (2P )| − | N (x0 ) ∩ V ( P )| ≥ 2k − ( k+2 1 − 2) ≥ 2, which implies that 2 there exist a path P of length at least 4 or at least two 3-paths P 0 and P 0 in P such that exactly the end vertices of P , or the end vertices of P 0 and P 0 are adjacent to x0 . Case 1.1. There exists a path P = y i . . . y j of length at least 4 in P such that exactly two end vertices of P are adjacent to x0 . Suppose that y 1 ∈ N ( y 0 ). If yk ∈ N ( y 0 ), then there exists a (k − 1)-path P 6 = y i +2 . . . yk y 0 y 1 . . . y i in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 6 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . If yk ∈ / N ( y 0 ), by (1), then there exists one vertex u 4 ∈ ( N ( y 0 ) ∩ N ( yk ) ∩ Y )\ V ( P ) such that P 7 = y i +3 . . . yk u 4 y 0 y 1 . . . y i is a (k − 1)-path in G [Y ], and | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 7 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . Hence, y 1 ∈ / N ( y 0 ). Similarly, yk ∈ / N ( y 0 ). 1 By (1) and | N ( y 0 ) ∩ X | < | N ( y 0 ) ∩ V ( P )| ≤ k+ , we have that |( N ( y 1 ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ | N ( y 1 ) ∩ N ( y 0 )| − 2 | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2 and |( N ( yk ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ | N ( yk ) ∩ N ( y 0 )| − | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2, and so there exists two distinct vertices u 5 ∈ ( N ( y 0 ) ∩ N ( y 1 ) ∩ Y )\ V ( P ) and u 6 ∈ ( N ( y 0 ) ∩ N ( yk ) ∩ Y )\ V ( P ). Then, P 8 = y i +4 . . . yk u 6 y 0 u 5 y 1 . . . y i is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 8 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . Case 1.2. There exist two 3-paths P 0 = y i y i +1 y i +2 y i +3 and P 0 = y j y j +1 y j +2 y j +3 in P such that exactly end vertices of P 0 and P 0 are adjacent to x0 , where i < j. Suppose that y 1 ∈ N ( y 0 ). If yk ∈ N ( y 0 ), then P 9 = y i +2 . . . yk y 0 y 1 . . . y i is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 9 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . If yk ∈ / N ( y 0 ), then, by (1), |( N ( yk ) ∩ N ( y 0 ) ∩

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

71

Fig. 1. Constructions of (k − 1)-paths.

Y )\ V ( P )| ≥ | N ( yk ) ∩ N ( y 0 )| − | N ( y 0 ) ∩ X | − | N ( y 0 ) ∩ V ( P )| ≥ 2, and there exists one vertex u 7 ∈ ( N ( y 0 ) ∩ N ( yk ) ∩ Y )\ V ( P ). Hence, P 10 = y i +3 . . . yk u 7 y 0 y 1 . . . y i is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 10 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, y 1 ∈ / N ( y 0 ). Similarly, yk ∈ / N ( y 0 ). Since | P 0 | = | P 0 | = 4, | V ( P )| ≥ 7, and so k ≥ 7. If y is nonadjacent to y 0 for any y ∈ Y , then, by (1), |( N ( y ) ∩ N ( y 0 ) ∩ 1 Y )\ V ( P )| ≥ 2k − 2 − ( k+ − 1) − k+2 1 = 2k − 2 k+2 1 − 1 ≥ k − 2 ≥ 5. Let u 8 ∈ ( N ( y 0 ) ∩ N ( y 1 ) ∩ Y )\ V ( P ), u 9 ∈ ( N ( y 0 ) ∩ 2 N ( yk ) ∩ Y )\ V ( P ) and u 8 = u 9 . If y j +3 ∈ / Y ≤k−1 , then, by yk ∈ N (x0 ) ∩ Y ≤k−1 , y j +3 = yk and P 11 = y j +4 . . . yk u 9 y 0 u 8 y 1 . . . y j is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 11 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . If y j +3 ∈ Y ≤k−1 and y j +3 is adjacent to y i +3 , then P 12 = y j . . . y i +3 y j +3 . . . yk u 9 y 0 u 8 y 1 . . . y i y i +1 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 12 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . If y j +3 ∈ Y ≤k−1 and y j +3 is nonadjacent to y i +3 , then |( N ( y j +3 ) ∩ N ( y i +3 ) ∩ Y )\ V ( P )| ≥ | N ( y j +3 ) ∩ N ( y i +3 )| − | N ( y j +3 ) ∩ X | − | N ( y j +3 ) ∩ V ( P )| ≥ 2k − 2 − (k − 1) − (k − 2) = 1. Combining this with |( N ( y ) ∩ N ( y 0 ) ∩ Y )\ V ( P )| ≥ k − 2 ≥ 5 for any y ∈ Y , we have three distinct vertices u 10 ∈ ( N ( y i +3 ) ∩ N ( y j +3 ) ∩ Y )\ V ( P ), u 11 ∈ ( N ( y 0 ) ∩ N ( yk ) ∩ Y )\ V ( P ) and u 12 ∈ ( N ( y 0 ) ∩ N ( y 1 ) ∩ Y )\ V ( P ). Let P 13 = y j . . . y i +3 u 10 y j +3 . . . yk u 11 y 0 u 12 y 1 . . . y i (see Fig. 1(b)). Then P 13 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 13 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . 1 Case 2. | N ( y 0 ) ∩ V ( P )| > k+ . 2 1 Since | N ( y 0 ) ∩ V ( P )| ≥ k+ + 1 and k+2 1 + 1 − 2k ≥ 1, there exists an integer i such that y i , y i +1 ∈ N ( y 0 ). If 2 y1 ∈ / N (x0 ) ∩ Y ≤k−1 , then P 14 = y 2 . . . y i y 0 y i +1 . . . yk is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V ( P 14 ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . Hence, y 1 ∈ N (x0 ) ∩ Y ≤k−1 . Similarly, yk ∈ N (x0 ) ∩ Y ≤k−1 . Noting that | N (x0 ) ∩ Y | = m ≤ k − 2, we have V ( P )\ N (x0 ) = ∅. We assume that y j ∈ V ( P )\ N (x0 ). If y 1 is adjacent to yk , then C 0 = y 1 . . . y i y 0 y i +1 . . . yk y 1 is a (k + 1)-cycle in G [Y ]. We can deduce that C 0 − y j is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V (C 0 − y j ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, y 1 is nonadjacent to yk . If y 1 , yk ∈ N ( y 0 ), then C 1 = y 0 y 1 . . . yk y 0 is a (k + 1)-cycle in G [Y ]. We have that C 1 − y j is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V (C 1 − y j ) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . So, | N ( y 0 ) ∩ V ( P )| ≤ k − 1. 1 Case 2.1. | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | < k+ . 2

| V ( P )| − | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | ≥ 2 − − 1) ≥ 1. Then, there exist a path P of length at least 4 or at least two 3-paths P 0 and P 0 in P such that exactly the end vertices of P , or the end vertices of P 0 and P 0 are in N (x0 ) ∩ Y ≤k−1 . If there exists a path P of length at least 4 in P such that exactly the end vertices of P are in N (x0 ) ∩ Y ≤k−1 , then there exist two vertices yl , yl+1 ∈ V ( P )\( N (x0 ) ∩ Y ≤k−1 ) such that |{ yl , yl+1 } ∩ { y i , y i +1 }| ≤ 1. If there exist at least two 3-paths P 0 and P 0 in P such that exactly the end vertices of P 0 and P 0 are in N (x0 ) ∩ Y ≤k−1 , then there exist two vertices yl , yl+1 ∈ V ( P )\( N (x0 ) ∩ Y ≤k−1 ) 1 Clearly, | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | ≤ k+ − 1. Note that y 1 , yk ∈ N (x0 ) ∩ Y ≤k−1 and 2

k+2 1

( k+2 1

such that |{ yl , yl+1 } ∩ { y i , y i +1 }| = 0. Since y 1 is nonadjacent to yk and y 1 , yk ∈ N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 , we can deduce that |( N ( y 1 ) ∩ N ( yk ) ∩ Y )\ V ( P )| ≥ | N ( y 1 ) ∩ N ( yk )| − | N ( yk ) ∩ X | − | N ( yk ) ∩ V ( P )| ≥ 2k − 2 − (k − 1) − (k − 2) = 1. Hence, there exists one vertex u 13 ∈ ( N ( y 1 ) ∩ N ( yk ) ∩ Y )\ V ( P ). Now, C 2 = y 1 . . . y i y 0 y i +1 . . . yk u 13 y 1 is a (k + 2)-cycle in G [Y ] (see Fig. 1(c)). Let P 15 = C 2 − { yl , yl+1 }. Then P 15 is a (k − 1)-path in G [Y ] such that | V ( P ) ∩ N (x0 ) ∩ Y ≤k−1 | < | V (C 2 − { yl , yl+1 }) ∩ N (x0 ) ∩ Y ≤k−1 |, a contradiction to the choice of P . 1 Case 2.2. | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | ≥ k+ . 2 Suppose that there exists a connected subgraph H of order k in G [Y ] such that

v ∈Y \ V ( H )

N ( v ) ∩ V ( H ) ≤

N ( v ) ∩ X .

v ∈Y \ V ( H )

By Lemma 2.2(i), G is λk -optimal.

72

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

In the following, we consider that there exists no connected subgraph H 0 of order k in G [Y ] such that

N ( v ) ∩ V ( H 0 ) ≤

v ∈Y \ V ( H 0 )

N ( v ) ∩ X .

v ∈Y \ V ( H 0 )

1 Since | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | ≥ k+ and y 0 ∈ N (x0 ) ∩ Y ≤k−1 , |Y ≤k−1 | ≥ k+2 1 + 1 = 2k + 1. Combining Y ≤k−1 ⊆ 2

N (x0 ) ∩ Y with x0 ∈ X m , we have 2k + 1 ≤ |Y ≤k−1 | ≤ k − 2. Let |Y ≤k−1 | = k − s. Clearly, 2 ≤ s ≤ 2k − 1. For any y ∈ Y , by | N (x0 ) ∩ Y | = min{| N (x) ∩ Y | : x ∈ X } ≤ min{| N ( y ) ∩ X | : y ∈ Y } and Y ≤k−1 ⊆ N (x0 ) ∩ Y , we can deduce that | N ( y ) ∩ X | ≥ | N (x0 ) ∩ Y | ≥ |Y ≤k−1 | = k − s. Claim 3. |Y | ≥ 2k − s. First suppose that G [Y ≤k−1 ] is connected. Since |Y ≤k−1 | ≤ k − 2 and G [Y ] is connected, there exists a connected subgraph H 1 of order k in G [Y ] such that Y ≤k−1 ⊆ V ( H 1 ). Recalling that | N ( y ) ∩ V ( H 1 )| ≤ k ≤ | N ( y ) ∩ X | for any y ∈ Y \ V ( H 1 ), we have that

N ( v ) ∩ V ( H 1 ) ≤

v ∈Y \ V ( H 1 )

N ( v ) ∩ X ,

v ∈Y \ V ( H 1 )

a contradiction. Next suppose that G [Y ≤k−1 ] is disconnected. Let G [ V 1 ], G [ V 2 ], . . . , G [ V t ] be the components of G [Y ≤k−1 ]. Then, there such that y and y are in distinct components, say y ∈ V and y ∈ V . We can deduce that | N ( y ) ∩ exists one vertex y 0 1 0 2 t N ( y 0 ) ∩ Y ≤k−1 | = i =1 | N ( y ) ∩ N ( y 0 ) ∩ V i | ≤ | N ( y 0 ) ∩ V 1 | + | N ( y ) ∩ V 2 | + · · · + | N ( y ) ∩ V t | = 0. By | N ( y ) ∩ N ( y 0 ) ∩ X | ≤ | N ( y 0 ) ∩ X | < | N ( y 0 ) ∩ V ( P )| ≤ k − 1, we have that

N y ∩ N ( y 0 ) ∩ Y \Y ≤k−1 = N y ∩ N ( y 0 ) ∩ Y − N y ∩ N ( y 0 ) ∩ Y ≤k−1 = N y ∩ N ( y 0 ) − N y ∩ N ( y 0 ) ∩ X ≥ 2k − 2 − (k − 2) = k. Therefore, we have that |Y \Y ≤k−1 | ≥ |( N ( y ) ∩ N ( y 0 ) ∩ Y )\Y ≤k−1 | ≥ k, and so |Y | = |Y ≤k−1 | + |Y \Y ≤k−1 | ≥ (k − s) + k = 2k − s. The proof of Claim 3 is complete. Claim 4. For any y ∈ Y \Y ≤k−1 , | N ( y ) ∩ Y ≤k−1 | ≤ k − 2s. Suppose, on the contrary, that there exists one vertex v 0 ∈ Y \Y ≤k−1 such that | N ( v 0 ) ∩ Y ≤k−1 | ≥ k − 2s + 1. If | N ( v 0 ) ∩ Y ≤k−1 | = k − s, then Y ≤k−1 ⊆ N ( v 0 ). Combining this with |Y ≤k−1 | ≤ k − 2, there exists a connected subgraph H 2 of order k in G [Y ] such that Y ≤k−1 ∪ { v 0 } ⊆ V ( H 2 ). Since | N ( y ) ∩ V ( H 2 )| ≤ k ≤ | N ( y ) ∩ X | for any y ∈ Y \ V ( H 2 ), we can deduce that

N ( v ) ∩ V ( H 2 ) ≤

v ∈Y \ V ( H 2 )

N ( v ) ∩ X ,

v ∈Y \ V ( H 2 )

a contradiction. Suppose that | N ( v 0 ) ∩ Y ≤k−1 | < k − s. Noting that |Y ≤k−1 | = k − s and | N ( v 0 ) ∩ Y ≤k−1 | ≥ k − 2s + 1, we have that |Y ≤k−1 \ N ( v 0 )| = |Y ≤k−1 | − | N ( v 0 ) ∩ Y ≤k−1 | ≤ k − s − (k − 2s + 1) = s − 1, which implies that there are at most s − 1 vertices of Y ≤k−1 are nonadjacent to v 0 . Since u is nonadjacent to v 0 for any u ∈ Y ≤k−1 \ N ( v 0 ), by assumption, | N (u ) ∩ N ( v 0 )| ≥ 2k − 2. As | N (u ) ∩ X | ≤ k − 1, we can deduce that | N (u ) ∩ N ( v 0 ) ∩ Y | = | N (u ) ∩ N ( v 0 )| − | N (u ) ∩ N ( v 0 ) ∩ X | ≥ 2k − 2 − (k − 1) = k − 1 ≥ 3, which implies that N (u ) ∩ N ( v 0 ) ∩ Y = ∅. Therefore, there exists a set U ⊆ Y ∩ N ( v 0 ) ∩ N (Y ≤k−1 \ N ( v 0 )) such that |U | ≤ |Y ≤k−1 \ N ( v 0 )| and G [Y ≤k−1 ∪ { v 0 } ∪ U ] is connected. Then, |Y ≤k−1 ∪ { v 0 } ∪ U | ≤ |Y ≤k−1 | + |{ v 0 }| + |U | ≤ k − s + 1 + s − 1 = k. Hence, there exists a connected subgraph H 3 of order k in G [Y ] such that Y ≤k−1 ∪ { v 0 } ∪ U ⊆ V ( H 3 ). Noting that | N ( y ) ∩ V ( H 3 )| ≤ k ≤ | N ( y ) ∩ X | for any y ∈ Y \ V ( H 3 ), we have that

N ( v ) ∩ V ( H 3 ) ≤

v ∈ X \V (H 3 )

N ( v ) ∩ X ,

v ∈Y \ V ( H 3 )

a contradiction. The proof of Claim 4 is complete. Let U 1 = { y ∈ Y \Y ≤k−1 : y is adjacent to every vertex of X ≤k−2 } and U 2 = Y \(Y ≤k−1 ∪ U 1 ). By the deﬁnition of U 1 and Y ≤k−1 ⊆ N (x) for any x ∈ X ≤k−2 , we have that |Y ≤k−1 | + |U 1 | ≤ k − 2. Since |Y ≤k−1 | = k − s, |U 1 | ≤ s − 2. Claim 5. For any u ∈ U 2 , | N (u ) ∩ X | ≥ k + s. By the deﬁnition of U 2 , there exists one vertex x∗ ∈ X ≤k−2 such that u is nonadjacent to x∗ . So, |( N (x∗ ) ∩ Y )\Y ≤k−1 | = | N (x∗ ) ∩ Y | − | N (x∗ ) ∩ Y ≤k−1 | = | N (x∗ ) ∩ Y | − |Y ≤k−1 | ≤ (k − 2) − (k − s) = s − 2. Recalling that u ∈ Y \Y ≤k−1 , by Claim 4, we can deduce that | N (u ) ∩ Y ≤k−1 | ≤ k − 2s. Therefore,

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

73

2k − 2

≤ N (u ) ∩ N x∗ = N (u ) ∩ N x∗ ∩ X + N (u ) ∩ N x∗ ∩ Y ≤k−1 + N (u ) ∩ N x∗ ∩ Y \Y ≤k−1 ≤ N (u ) ∩ X + N (u ) ∩ Y ≤k−1 + N x∗ ∩ Y \Y ≤k−1 ≤ N (u ) ∩ X + (k − 2s) + (s − 2).

Therefore, | N (u ) ∩ X | ≥ k + s. The proof of Claim 5 is complete. Let U 3 = (Y \ V ( P )) ∩ Y ≤k−1 , U 4 = (Y \ V ( P )) ∩ U 1 and U 5 = (Y \ V ( P )) ∩ U 2 . It is easy to see that Y \ V ( P ) = U 3 ∪ U 4 ∪ U 5 . 1 As | N (x0 ) ∩ V ( P ) ∩ Y ≤k−1 | ≥ k+ , we have that |Y ≤k−1 ∩ V ( P )| ≥ k+2 1 = 2k . Then |U 3 | = |(Y \ V ( P )) ∩ Y ≤k−1 | = 2

|Y ≤k−1 | − |Y ≤k−1 ∩ V ( P )| ≤ k − s − 2k = 2k − s. Combining Claim 3 with |U 1 | ≤ s − 2, we have that |U 5 | = |Y | − | V ( P )| − |U 4 | − |U 3 | ≥ |Y | − | V ( P )| − |U 1 | − |U 3 | ≥ (2k − s) − k − (s − 2) − ( 2k − s) = 2k − s + 2 > |U 3 |. Since | N ( y ) ∩ X | ≥ k − s for any y ∈ Y , | N (u ) ∩ X | ≥ k + s for any u ∈ U 5 ⊆ U 2 , | N (u ) ∩ X | ≥ k for any u ∈ U 4 ⊆ U 1 , y 0 ∈ U 3 and | N ( y 0 ) ∩ V ( P )| ≤ k − 1, we can deduce that

N ( v ) ∩ V ( P )

v ∈Y \ V ( P )

=

N ( v ) ∩ V ( P )

v ∈U 3 ∪U 4 ∪U 5

< k|U 3 | + k|U 4 | + k|U 5 | < (k − s)|U 3 | + k|U 4 | + (k + s)|U 5 | N (v ) ∩ X + N (v ) ∩ X + N (v ) ∩ X ≤ v ∈U 3

=

v ∈U 4

v ∈U 5

N ( v ) ∩ X .

v ∈Y \ V ( P )

By Lemma 2.2(ii), a contradiction.

2

Lemma 3.3. Let k ≥ 4 be an integer and let G be a λk -connected graph of order at least 2k satisfying | N (u ) ∩ N ( v )| ≥ 2k − 2 for all pairs u , v of nonadjacent vertices, and let S = [ X , Y ] be a λk -cut of G. G is λk -optimal if one of the following two conditions holds: (a) X ≤k−2 = ∅ and | X k−1 | ≤ k − 1, (b) Y ≤k−1 \Y k−1 = ∅ and |Y k−1 | ≤ k − 1. Proof. By Lemma 2.1, λk (G ) ≤ ξk (G ). If | X | = k or |Y | = k, then we are done. Next, suppose that | X | ≥ k + 1 and |Y | ≥ k + 1. Without loss of generality, it suﬃces to consider the case that X ≤k−2 = ∅ and | X k−1 | ≤ k − 1. As G [ X ] is connected, there exists a connected subgraph H 0 of order k in G [ X ] such that V ( H 0 ) contains as many vertices in X k−1 as possible. If X k−1 ⊆ V ( H 0 ), then | N (u ) ∩ Y | ≥ k for any u ∈ X \ V ( H 0 ). Therefore,

N ( v ) ∩ V ( H 0 ) ≤

v ∈ X \V (H 0 )

N ( v ) ∩ Y .

v ∈ X \V (H 0 )

By Lemma 2.2(i), G is λk -optimal. Now, we consider X k−1 \ V ( H 0 ) = ∅. Since | X k−1 | ≤ k − 1, there exists one vertex x1 ∈ V ( H 0 ) and x1 ∈ / X k−1 . If there exists one vertex u 0 ∈ X k−1 \ V ( H 0 ) such that | N (u 0 ) ∩ V ( H 0 )| = k, then H 1 = G [ V ( H 0 ) ∪ {u 0 }] − {x1 } is a connected subgraph of order k in G [ X ] such that | X k−1 ∩ V ( H 1 )| > | X k−1 ∩ V ( H 0 )|, a contradiction to the choice of H 0 . So, | N (x) ∩ V ( H 0 )| ≤ k − 1 = | N (x) ∩ Y | for any x ∈ X k−1 \ V ( H 0 ). Since | N (u ) ∩ V ( H 0 )| ≤ | N (u ) ∩ Y | for any u ∈ X \ V ( H 0 ), we have that

N ( v ) ∩ V ( H 0 ) ≤

v ∈ X \V (H 0 )

By Lemma 2.2(i), G is λk -optimal.

N ( v ) ∩ Y .

v ∈ X \V (H 0 )

2

Proof of Theorem 1.2. Since k ≥ 2, 2k − 2 ≥ k. By Lemma 2.1, G is λk -connected and λk (G ) ≤ ξk (G ). Let S = [ X , Y ] be a λk -cut of G. So G [ X ] and G [Y ] are connected. If | X | = k or |Y | = k, then we are done. Now, let | X | ≥ k + 1 and |Y | ≥ k + 1. When k = 2, by Theorem 1.1, then we are done. Next, assume that k ≥ 3. We consider the following cases.

74

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

Case 1. X ≤k−2 = ∅ or Y ≤k−1 \Y k−1 = ∅. Without loss of generality, suppose that min{| N (x) ∩ Y | : x ∈ X } ≤ min{| N ( y ) ∩ X | : y ∈ Y }. First suppose that X ≤k−2 = ∅. If k = 3, then, by Corollary 2.4, G is λ3 -optimal. If k ≥ 4, then, by Lemma 3.2, G is λk -optimal. Next suppose that Y ≤k−1 \Y k−1 = ∅. Since min{| N (x) ∩ Y | : x ∈ X } ≤ min{| N ( y ) ∩ X | : y ∈ Y }, we have that X ≤k−2 = ∅. By Corollary 2.4 and Lemma 3.2, G is λk -optimal. Case 2. X ≤k−2 = ∅ and Y ≤k−1 \Y k−1 = ∅. Without loss of generality, suppose that | X | ≤ |Y |. Note that X ≤k−2 = ∅ and Y ≤k−1 \Y k−1 = ∅. If | X k−1 | ≤ k − 1 or |Y k−1 | ≤ k − 1, then, by Corollary 2.5 and Lemma 3.3, G is λk -optimal. In the following, we consider the case that | X k−1 | ≥ k and |Y k−1 | ≥ k. Case 2.1. E (G [ X k−1 ]) = ∅. Let u ∈ X k−1 . Since G [ X ] is connected, there exists a connected subgraph H of order k in G [ X ] such that u ∈ V ( H ). As E (G [ X k−1 ]) = ∅, we have that | N (x) ∩ V ( H )| ≤ k − 1 = | N (x) ∩ Y | for any x ∈ X k−1 \ V ( H ). By the assumption, we know that | N (x) ∩ V ( H )| ≤ k ≤ | N (x) ∩ Y | for any x ∈ X k \ V ( H ). Therefore,

N ( v ) ∩ V ( H ) ≤

v ∈ X \V (H )

N ( v ) ∩ Y .

v ∈ X \V (H )

By Lemma 2.2(i), G is λk -optimal. Case 2.2. There exist u , v ∈ X k−1 such that uv ∈ E (G [ X ]). It is easy to see that there exists a connected subgraph H of order k in G [ X ] such that uv ∈ E ( H ). Case 2.2.1. N (u ) ∩ N ( v ) = ∅. Since N (u ) ∩ N ( v ) = ∅, we can deduce that | N (x) ∩ V ( H )| ≤ k − 1 for any x ∈ X \ V ( H ). If X k \ V ( H ) = ∅, then

N ( v ) ∩ V ( H ) ≤ (k − 1) X \ V ( H ) <

v ∈ X \V (H )

N ( v ) ∩ Y .

v ∈ X \V (H )

By Lemma 2.2(ii), a contradiction. So, X \ V ( H ) ⊆ X k−1 . Therefore,

N ( v ) ∩ V ( H ) ≤ (k − 1) X \ V ( H ) =

v ∈ X \V (H )

N ( v ) ∩ Y .

v ∈ X \V (H )

By Lemma 2.2(i), G is λk -optimal. Case 2.2.2. N (u ) ∩ N ( v ) = ∅. Since | X | ≤ |Y |, | X | ≤ ν (2G ) . Clearly, d(u ) = | N (u ) ∩ X | + | N (u ) ∩ Y | ≤ | X | − 1 + (k − 1) ≤ ν (2G ) + k − 2. Similarly,

d( v ) ≤ ν (2G ) + k − 2. By the hypothesis, for any x ∈ N (u ) ∩ N ( v ) ∩ X , we have that d(x) ≥ ν (2G ) + k − 1, and so | N (x) ∩ Y | =

d(x) − | N (u ) ∩ X | ≥ 2 + k − 1 − (| X | − 1) ≥ k. Let u ∈ X \ V ( H ). If | N (u ) ∩ V ( H )| = k, then u ∈ N (u ) ∩ N ( v ) ∩ X . Thus, | N (u ) ∩ V ( H )| = k ≤ | N (u ) ∩ Y |. If | N (u ) ∩ V ( H )| ≤ k − 1, then, by X ≤k−2 = ∅, | N (u ) ∩ V ( H )| ≤ | N (u ) ∩ Y |. Therefore, ν (G )

N ( v ) ∩ V ( H ) ≤

v ∈ X \V (H )

N ( v ) ∩ Y .

v ∈ X \V (H )

By Lemma 2.2(i), G is λk -optimal.

2

The complete graphs, complete bipartite graphs and Harary graphs are important classes of graphs. As applications of Theorem 1.2, we will show that these graphs are λk -optimal. A complete graph G is a simple graph in which any two vertices are adjacent. Corollary 3.4. Let k ≥ 2 be an integer, and let G be a complete graph of order at least 2k. Then G is λk -optimal. Proof. Since G is a complete graph, each two vertices u and v are adjacent. Note that ν (2G ) + k − 1 for any u ∈ V (G ). By Theorem 1.2, G is λk -optimal. 2

ν (G ) ≥ 2k. Then d(u ) = ν (G ) − 1 ≥

A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and one end in Y ; such a partition ( X , Y ) is called a bipartition of the graph, and X and Y its parts. We denote a bipartite graph G with bipartition ( X , Y ) by G [ X , Y ]. If G [ X , Y ] is simple and every vertex in X is joined to every vertex in Y , then G is called a complete bipartite graph. Corollary 3.5. Let k ≥ 2 be an integer, and let G [ X , Y ] be a complete bipartite graph of order at least 2k. If | X | ≥ 2k − 2 and |Y | ≥ 2k − 2, then G [ X , Y ] is λk -optimal.

S. Wang, L. Zhang / Theoretical Computer Science 557 (2014) 66–75

75

Fig. 2. H 5,7 .

Proof. By deﬁnition, G [ X , Y ] has no triangles, and two vertices u and v are nonadjacent if and only if u , v are in the same part. Thus, for all pairs u , v of nonadjacent vertices, | N (u ) ∩ N ( v )| ≥ min{| X |, |Y |} ≥ 2k − 2. By Theorem 1.2, G [ X , Y ] is λk -optimal. 2 Let n > m > 0 be two positive integers. A Harary graph H m,n has vertex set { v 0 , v 1 , . . . , v n−1 }. According to the parities of m and n, there are three types of Harary graphs. In the following, additions are all taken modulo n. Type 1. When m is even, suppose m = 2r. Two vertices v i and v j of H 2r ,n are adjacent if and only if |i − j | ≤ r. Type 2. When m is odd and n is even, suppose m = 2r + 1. Then H 2r +1,n is obtained from H 2r ,n by adding edges { v i v i + n : 2

i = 0, 1, . . . , n2 − 1}. Type 3. When m and n are both odd, suppose m = 2r + 1. Then H 2r +1,n is obtained from H 2r ,n by adding edges { v i v i + n+1 : 2

3 i = 0, 1, . . . , n− } ∪ { v 0 v n−1 }. The Harary graph H 5,7 is shown in Fig. 2. 2 2

Corollary 3.6. Let k ≥ 2 be an integer, and let G be the Harary graph H m,n . If n ≥ 2k and m ≥

n 2

+ k − 1, then G is λk -optimal.

Proof. By the deﬁnition of the Harary graph, δ( H m,n ) ≥ m ≥ n2 + k − 1. For all pairs u , v of nonadjacent vertices, we can deduce that | N (u ) ∩ N ( v )| = | N (u )| +| N ( v )| −| N (u ) ∪ N ( v )| ≥ 2m −(n − 2) ≥ 2k > 2k − 2. By Theorem 1.2, G is λk -optimal. 2 References [1] C. Balbuena, M. Cera, A. Diánez, P. García-Vázquez, X. Marcote, On the restricted connectivity and superconnectivity in graphs with given girth, Discrete Math. 307 (6) (2007) 659–667. [2] C. Balbuena, A. Carmona, J. Fàbrega, M.A. Foil, Superconnectivity of bipartite digraphs and graphs, Discrete Math. 197–198 (1999) 61–75. [3] C. Balbuena, P. García-Vázquez, X. Marcote, Suﬃcient conditions for λ -optimality in graphs with girth g, J. Graph Theory 52 (1) (2006) 73–86. [4] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, New York, 2007. [5] C. Balbuena, X. Marcote, P. García-Vázquez, On restricted connectivities of permutation graphs, Networks 45 (3) (2005) 113–118. [6] F.T. Boesch, On unreliability polynomials and graph connectivity in reliable network synthesis, J. Graph Theory 10 (3) (1986) 339–352. [7] Paul Bonsma, Nicola Ueﬃng, Lutz Volkmann, Edge-cuts leaving components of order at least three, Discrete Math. 256 (1–2) (2002) 431–439. [8] Nai-Wen Chang, Sun-Yuan Hsieh, {2, 3}-Extraconnectivities of hypercube-like networks, J. Comput. System Sci. 79 (5) (2013) 669–688. [9] Nai-Wen Chang, Cheng-Yen Tsai, Sun-Yuan Hsieh, On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes, IEEE Trans. Comput. 63 (6) (2014) 1593–1599. [10] Hanyuan Deng, Jianer Chen, Qiaoliang Li, Rongheng Li, Qiju Gao, On the construction of most reliable networks, Discrete Appl. Math. 140 (1–3) (2004) 19–33. [11] Abdol-Hossein Esfahanian, S. Louis Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (4) (1988) 195–199. [12] J. Fàbrega, M.A. Foil, Extraconnectivity of graphs with large girth, Discrete Math. 127 (1–3) (1994) 163–170. [13] Sun-Yuan Hsieh, Ying-Hsuan Chang, Extraconnectivity of k-ary n-cube networks, Theoret. Comput. Sci. 443 (20) (2012) 63–69. [14] Won-Sin Hong, Sun-Yuan Hsieh, Extra edge connectivity of hypercube-like networks, Int. J. Parallel Emergent Distrib. Syst. 28 (2) (2013) 123–133. [15] Angelika Hellwig, Lutz Volkmann, Maximally edge-connected and vertex-connected graphs and digraphs: a survey, Discrete Math. 308 (15) (2008) 3265–3296. [16] Angelika Hellwig, Lutz Volkmann, Suﬃcient conditions for λ -optimality in graphs of diameter 2, Discrete Math. 283 (1–3) (2004) 113–120. [17] Qinghai Liu, Xiaohui Huang, Zhao Zhang, Optimally restricted edge connected elementary Harary graphs, Theoret. Comput. Sci. 497 (2013) 131–138. [18] Jixiang Meng, Optimally super-edge-connected transitive graphs, Discrete Math. 260 (1–3) (2003) 239–248. [19] Jixiang Meng, Youhu Ji, On a kind of restricted edge connectivity of graphs, Discrete Appl. Math. 117 (1–3) (2002) 183–193. [20] Jianping Ou, Edge cuts leaving components of order at least m, Discrete Math. 305 (1–3) (2005) 365–371. [21] Li Shang, Heping Zhang, Super restricted edge-connectivity of graphs with diameter 2, Discrete Appl. Math. 161 (3) (2013) 445–451. [22] Ming Wang, Qiao Li, Conditional edge connectivity properties, reliability comparisons and transitivity of graphs, Discrete Math. 258 (1–3) (2002) 205–214. [23] Shiying Wang, Shangwei Lin, Chunfang Li, Suﬃcient conditions for super k-restricted edge connectivity in graphs of diameter 2, Discrete Math. 309 (4) (2009) 908–919. [24] Shiying Wang, Shangwei Lin, Suﬃcient conditions for a graph to be super restricted edge-connected, Networks 51 (3) (2008) 200–209. [25] Shiying Wang, Jing Li, Lihong Wu, Shangwei Lin, Neighborhood conditions for graphs to be super restricted edge connected, Networks 56 (1) (2010) 11–19. [26] Shiying Wang, Lei Zhang, Shangwei Lin, A neighborhood condition for graphs to be maximally k-restricted edge connected, Inform. Process. Lett. 112 (3) (2012) 95–97. [27] Zhao Zhang, Jinjiang Yuan, A proof of an inequality concerning k-restricted edge connectivity, Discrete Math. 304 (1–3) (2005) 128–134.