Xdxb.xju.edu.cn

Journal of Xinjiang University(Natural Science Edition) LIN Hui-qiu, MENG Ji-xiang†, TIAN Ying-zhi (College of Mathematics and Systems Science, Xinjiang University, Urumqi, Xinjiang 830046, China) A subset S ⊂ E(G) is called a 4-restricted-edge-cut of G, if G − S is disconnected and every component contains at least 4 vertices. The minimum cardinality over all 4-restricted-edge-cut of G is called the 4-restricted-edge connectivity of G, denoted by λ4(G). In this paper, we prove that λ4(Qn) = 4n − 8.
Similarly, a subset F ⊂ V (G) is called a Rg-vertex cut of G, if G − F is disconnected and each vertex u ∈ V (G) − F has at least g neighbors in G − F . The minimum cardinality of all Rg-vertex-cut is called the Rg-vertex connectivity of G, denoted by κg(G). In this paper, we prove that κ1(L(Qn)) = 3n − 4,κ2(L(Qn)) = 4n − 8, where L(Qn) is the line graph of Qn.
Key words line graph; hypercube; restricted-edge-cut; restricted-edge-connectivity κ1(L(Qn)) = 3n − 4 κ2(L(Qn)) = 4n − 8 Let G = (V, E) be a finite graph without loops and parallel edges. It is well know that the underlying topology of a computer interconnection network is modeled by a graph G, and the connectivity κ(G) orthe edge connectivity λ(G) of G is an important measure for fault-tolerance of the network. In general,the larger κ(G) or λ(G) is, the more reliable the network is. However, κ(G) or λ(G) is the worst measurethat underestimates the resilience of the network. To overcome such shortcoming, Harary [1] introduced theconcept of conditional connectivity by putting some requirements on the components of G − F .
Hypercubes are used as fundamental models for computer networks. There are many research articles on the hypercubes (see, for example[2,3,4,5]). An n-dimensional hypercube is an undirected graph Qn = (V,E)with |V | = 2n and |E| = n2n−1. Each vertex can be represented by an n-bit binary string. There is an edgebetween two vertices whenever their binary string representation differ in only one bit position. It is well know Foundation Item The research is supported by NSFC (No.10671165).
Biography LIN Hui-qiu(1983-), Male, Master.
† Corresponding author E-mail: [email protected] that λ(Qn) = n. A subset S ⊆ E(G) is called a m-restricted-edge-cut of G if G−S is disconnected and everycomponent contains at least m vertices. λm is the minimum cardinality over all m-restricted-edge-cuts. It iswell known that λ2(Qn) = 2n−2 and λ3(Qn) = 3n−4 (see[2,3]). In this paper, we show that λ4(Qn) = 4n−8,for n ≥ 4. With every graph G which is nonempty, there is associated a graph L(G), called the line-graph ofG, whose point set can be put in one to one correspondence with the edge set of G in such a way that twopoints of L(G) are adjacent if and only if the corresponding edges of G are adjacent. A subset F ⊂ V (G) iscalled a Rg-vertex cut of G, if G − F is disconnected and each vertex u ∈ V (G) − F has at least g neighborsin G − F . The cardinality of a minimum Rg-vertex-cut of G, denoted by κg(G). There are many researcharticles on the connectivity of line graph (see, for example[6,7]). We follow Bondy [8] for terminologies notgiven here.
4-restricted-edge connectivity of hypercubes We express Qn as Qn = L ⊕ R, where L and R are (n − 1)-subcubes of Qn induced by the vertices with the leftmost coordinate 0 and 1, respectively, that is, all the vertices in L are the form 0Xn−1 and all thevertices in R are of the form 1Xn−1. Edges are also labelled from 0 to n − 1 such that any edge labelled iconnects two vertices whose labels differ in the ith bit. Since the first bit position is the 0th position, soall the edges labelled 0 are cross edges. The neighbors of a vertex u are called bordering vertices of u. Thebordering vertex of u across dimension i is denote by ui. The bordering vertex of ui across dimension j isdenoted by uij. Similarly, the neighboring edges of a vertex of a node u are called bordering edges u, thebordering edges of u across dimension i is denoted by ei(u), since e0(u) is a cross edge, we also denote eo(u)by ec(u). ω(A) denote all the edges with one endpoint in A.
Theorem 2 λ4(Qn) = 4n−8, for n ≥ 4.
Proof Let S = ω(C4). Then |S| = |ω(C4)| = 4n − 8. We now verify that S is a 4-restricted-edge-cut of Qn. It is easy to see that Qn − C4 is connected(For any C4 ⊆ Qn, we can find an expression as Qn = L ⊕ R,such that C4 ⊆ V (L) or C4 ⊆ V (R). Since vertices in V (L) and V (R) are one-to-one corresponding, wehave Qn − C4 is connected ). And for any n ≥ 4, |V (Qn − C4)| ≥ 4, so S is a 4-restricted-edge-cut. Thus,λ4 ≤ |S| = |ω(C4)| = 4n−8. To show that λ4(Qn) = 4n−8, it is sufficient to show that λ4(Qn) ≥ 4n−8, whichwill discussed by contradiction in the following paragraphs.
Suppose A ⊆ E(G) ,|A| ≤ 4n − 9 and every component of Qn − A has at least four vertices. In the following, we will prove that Qn − A is connected. Let AL = A ∩ E(L), AR = A ∩ E(R). Since L ∩ R = ∅,|AL| + |AR| ≤ 4n − 9, then either |AL| ≤ 2n − 5 or |AR| ≤ 2n − 5. Without loss of generality, we suppose that|AR| ≤ 2n−5. In the following, we will prove that the vertices in R−AR is connected to each other in Qn−A.
Case 1 If there is no isolated vertex in R − AR, since λ (R) = λ (Qn−1) = 2n − 4 > 2n − 5 ≥ |AR|, we have that R − AR is connected.
Case 2 If there exists an isolated vertex uR in R−AR, then λ(R−uR) ≥ κ(R−uR) ≥ κ(R)−1 = n−2, and |AR|−dR(uR) ≤ n−4. Thus R−uR is connected. In the following we will prove that uR is connected to thesubgraph R−AR−uR in Qn−A. Since there is no isolated vertex in Qn−A, the cross edge ec(uR) = (uR,uL) ∈ A.
For 1 ≤ i ≤ n − 1, if there exists an i such that both ei(uL) ∈ A and ec(ui ) ∈ A, then u to G by the path: uRuLui ui , we are done. So we may suppose that for each i at least one of e ec(ui ) ∈ A. Let B = {e )|i = 1, 2, · · · , n − 1} ∩ A, then |B| ≥ n − 1. Since there is no isolated edge i(uL), ec(uiL in Qn − A, there exists a j such that ej(uL) = (uL,vL) ∈ AL. If both ei(vL) and ec(vi ) do not belongs to A, then we are done. So we suppose that at least one edge from each of the above n−2 pairs belongs to A. LetC = {ei(vL),ec(vi )|i = 1,2,··· ,n − 1 but i = j}. Then |C| ≥ n − 2. Since every component of Q vertices, so D = ω(ej(uL)) − AR = ∅. Suppose that wL is an edge set of an element of D, and wL ∈ {uL,vL}.
LIN Hui-qiu, et al.: Restricted Connectivity of the Line Graph of Hypercube Since there is no triangle in Qn, the vertex wL can be adjacent to just one of the two vertices uL, vL. LetE = {ei(wL),ec(wi )|i = 1,2,··· ,n − 1 and e iwLis not adjacet to uL or vL}. Since B, C , D, E are disjoint to each other, we have |E∩A| ≤ |A|−dR(uR)−|B|−|C| ≤ n−4. Since there are n−2 pairs of edges in E, so thereexists an i1 such that neither ei (v R can be connected to G[(R−AR)−uR] through the path P = uRuLvLvi1vi1, thus completing our proof that the vertices in R − A In the following paragraph, we will prove that any vertex of L−AL is connected to the subgraph R−AR.
Suppose that xL is any vertex in L−AL, if ec(xL) ∈ A, then we are done. So we suppose that ec(xL) ∈ A.
If there exists an i ∈ {1, 2, · · · , n − 1} such that both ei(xL) ∈ A and ec(xi(L)) ∈ A, then we are done. So wesuppose that at least one edge from each of the above n−1 pairs belongs to A. Let B = {ei(xL),ec(xi(L))|i =1, 2, · · · , n − 1} ∩ A, then |B | ≥ n − 1. Since there is no isolated vertex in Qn − A, there exists a j = i suchthat ej(xL) ∈ A. Suppose that ej(xL) = (xL,yL). For all i ∈ {1,2,··· ,n − 1} and i = j, if both ei(yL) ∈ A andec(yi ) ∈ A, then we are done. So we suppose that at least one edge from each of the above n−2 pairs belongs to A. Let C = {ei(yL),ec(yi )|i = 1,2,···n − 1 and i = j} ∩ A, then |C | ≥ n − 2. Since there is no isolated edge in Qn −A and Qn contains no triangle, without loss of generality, we suppose that ek = (xL,wL) ∈ A. Ifboth ei(wL) ∈ A and ec(wi ) ∈ A, then we are done. So we suppose that at least one edge from each above n − 2 pairs belongs to A. Let D = {ei(wL),ec(wi )|i = 1,2,···n − 1 and i = k}, then |D | ≥ n − 2. Since every component of Qn−A has at least four vertices, we have ω({xL,yL,wL})−AR = ∅ and zL ∈ {xL,yL,wL}. Sincethere is no triangle in Qn, then the vertex zL at most adjacent to two of the vertices {xL,yL,wL}.
If zL is adjacent to one of {xL,yL,wL}, without loss of generality, let el = (zL,yL). If both ei(wL) ∈ A and ec(wi ) ∈ A, then we are done. So we suppose at least one edge from each of the above n−2 pairs belongs to A. Let E = {ei(zL),ec(zi )|i = 1,2,··· ,n − 1 and i = j}, then |E | ≥ n − 2. Since e disjoint to each other, so |E ∩ A| ≤ n − 5. Since there are n − 2 pairs of edges in E , so there exists an i1such that neither zi (z ) belonging to A. Thus we are done. If z L are adjacent to yL and wL, let el = (zL,xL) and em = (zL,wL). If both ei(zL) ∈ A and ec(zi ) ∈ A, then we are done. So at least one edge from each of the above n − 3 pairs belongs to A. Let E = {ei(zL),ec(zi )|i = 1,2,.,n − 1 and i = l and m}.
Since ec(xL),B ,C ,D are disjoint to each other, so |E ∩ A| ≤ n − 5. Since there are n − 3 pairs of edges inE , so there exists an i1 such that neither ei (z ) belonging to A. Thus we are done.
In the following, we shall determine κ1(L(Qn)) and κ2(L(Qn)).
Lemma 1[9] Let X = L(Y ) be a connected graph. Then X −F contains exactly two components, if F is the minimum restricted-vertex-cut of G.
For a subset E ⊆ E(G), we use G[E ] to denote the edge-induced subgraph of G by E . Let L1 be a subgraph of L(G) and E1 = V (L1). Define G1 = G[E1].
Lemma 2[9] If L1 is a connected subgraph of L with at least two vertices, then the subgraph G1 ⊆ G is connected and |V (G1)| ≥ 3.
Lemma 3 For each u, v ∈ V (L(Qn)), if u,v is not adjacent, then |N(u)∩N(v)| ≤ 2.
Proof By contradiction, if |N (u) ∩ N (v)| ≥ 3, then each pair of disjoint edges in Qn has at least three crossing edges, which will induce a triangle. It is impossible, so |N (u) For any e ∈ E(LQn), |N(e)| = 3n−4. Next we prove that κ1(L(Qn)) = 3n−4.
Theorem 2 κ1(L(Qn)) = 3n−4, for n ≥ 4.
Proof First, we verify that κ1(L(Qn)) ≤ 3n−4. Let F be the set of all neighbors of some edge e. Denote F = N (e), then L(Qn)−F is disconnected, and |F | = 3n−4. We now verify that F is a R1-restricted-vertex cut.
Set e = uv, and for each vertex z ∈ L(Qn)−F −e. Since |N(z) N(u)| ≤ 2 and |N(z) N(v)| ≤ 2 by lemma 1.
Then dL(Qn)−F−e(z) ≥ 2n−2−4 = 2n−6 > 1. Then F is a restricted-vertex-cut. So κ1(L(Qn)) ≤ |F | = 3n−4.
We now show that κ1(L(Qn)) ≥ 3n − 4. By contradiction, suppose that F is the minimum restricted- vertex-cut, with F ⊆ R1, |F | ≤ 3n−5. Then L(Qn)−F has exactly two components by Lemma 1. We denotethem by L1 and L2, and |V (L1)|,|V (L2)| ≥ 2, then by Lemma 2, we have |V (G1)| ≥ 3,|V (G2)| ≥ 3 and bothG1 and G2 are connected. Thus S is a 3-restricted edge cut with |S| = |F | ≥ 3n − 4, it is a contradiction.
Therefore we get that κ1(L(Qn)) = 3n−4.
Lemma 4 For any vertex u, v ∈ V (L(Qn)), if u is adjacent to v, then |N(u) N(v)| = n−2.
Proof Let e = uv = (xy, yz), then u = xy has neighbors of (xx1,xx2,··· ,xxn−1,yy1,yy2,··· ,yyn−1), v = yz has neighbors of (yy1,yy2,··· ,yyn−1,zz1,zz2,··· ,zzn−1). Therefore |N(u) N(v)| = n−2.
Clearly, if uv ∈ E(L(Qn)), then |N(u) N(v)| = 0. By Lemma 4, we know that for any C4 ⊆ V (LQn), |N (C4)| = 4n−8. Next we proof that κ2(L(Qn)) = 4n−8.
Theorem 3 κ2(L(Qn)) = 4n−8, for n ≥ 4.
Proof First, we verify that κ2(L(Qn)) ≤ 4n − 8. Let F be the set of all neighbors of C4 in L(Qn).
Denoted by F = N (C4). Then L(Qn)−F is disconnected, and |F | = |N(C4)| = 4n−8. We now verify that F isa R2-restricted-vertex-cut. By Theorem 1, we know that Qn−ω(C4)−C4 is connected. Then L(Qn)−F −C4 isalso connected, for any n ≥ 4. Now we have to verify that for any vertex u ∈ L(Qn)−F−C4, dL(Q By contradiction, if there exist a vertex u ∈ L(Qn)−F −C4, such that dL(Q vertex x ∈ V (Qn) − C4 such that dV (Q (x) = 1, thus, d (x) = n − 1 ≥ 3, which is impossible. Therefore, (u) ≥ 2, then F ⊆ R2. So κ2(L(Q n)) ≤ 4n − 8.
On the other hand, we show that κ2(L(Qn)) ≥ 4n − 8. For this purpose, by contradiction, L1 is a connected subset of L(Qn), and F = N(L1) is a R2-restricted-vertex-cut with |F | < 4n − 8, dL (u) ≥ 2 and (v) ≥ 2, for any u ∈ L n)−N (L1)−L1 1,v ∈ V (L(Qn)) − V (N (L1)) − V (L1). Then |V (L1)| ≥ 3 and |V (L2)| ≥ 3.
Since Qn is triangle-free, we have |V (G1)| ≥ 4 and |V (G2)| ≥ 4, then S is a 4-restricted edge cut of Qn. ByTheorem 1, we have |S| ≥ 4n − 8, then |F | = |S| ≥ 4n − 8, a contradiction. Therefore, κ2(L(Qn)) ≥ 4n−8.
[1] Harary F. Conditional connectivity [J]. Networks, 1983, 26: 347-357.
[2] Esfahanian A N. Generalized measures of fault tolerance with application to n-cube networks [J]. IEEE Trans. Comput, [3] Zhu Q, Xu J M. On the restricted edge connectivity and extra edge connectivity of hypercubes and folded-hypercubes[J].
Journal of Univercity of Siciece and Techology of China, 2006, 36(3):249-253.
[4] Yang W H, Meng J X. Extraconnectivity of Hypercubes[J]. Applied mathmatics Letters, 2009, 22: 887-891.
[5] Latifi S, Hegde M, Naraghi-Pour M. Conditional connectivity Measures for Large Multiprocessor Systems [J]. IEEE Trans [6] Hellwig A, Rautenbach D, Volkmann L. Note on the connectivity of line graphs [J]. Inform Process Lett, 2004, 91(1): 7-10.
[7] Meng J X. Superconnectivity and super edge-connectivity of line graphs[J]. Graph Theory Notes of New York, 2001, XL, [8] Bondy J A, Murty U S R. Graph theory with application [M]. London: Macmillan, 1976.
[9] Xu J M, Lu Min, Meijie Ma and Angelika Hellwig. Super connectivity of line graph [J]. Information Processing Letters,

Source: http://xdxb.xju.edu.cn/qkbj/journal/rleasepdf/B/201001/B2010121100004.pdf