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) = 4
n − 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)) = 3
n − 4,
κ2(
L(
Qn)) = 4
n − 8, where
L(
Qn) is the line graph of
Qn.
Key words
line graph; hypercube; restricted-edge-cut; restricted-edge-connectivity
κ1(
L(
Qn)) = 3
n − 4
κ2(
L(
Qn)) = 4
n − 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 | = 2
n and
|E| =
n2
n−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: mjx@xju.edu.cn
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) = 2
n−2 and
λ3(
Qn) = 3
n−4 (see[2,3]). In this paper, we show that
λ4(
Qn) = 4
n−8,for
n ≥ 4. With every graph
G which is nonempty, there is associated a graph
L(
G), called the line-graph of
G, 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 0
Xn−1 and all thevertices in
R are of the form 1
Xn−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) = 4
n−8, for
n ≥ 4.
Proof Let
S =
ω(
C4). Then
|S| =
|ω(
C4)
| = 4
n − 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)
| = 4
n−8. To show that
λ4(
Qn) = 4
n−8, it is sufficient to show that
λ4(
Qn)
≥ 4
n−8, whichwill discussed by contradiction in the following paragraphs.
Suppose
A ⊆ E(
G) ,
|A| ≤ 4
n − 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| ≤ 4
n − 9, then either
|AL| ≤ 2
n − 5 or
|AR| ≤ 2
n − 5. Without loss of generality, we suppose that
|AR| ≤ 2
n−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) = 2
n − 4
> 2
n − 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. Let
C =
{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. Let
E =
{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 =
uRuLvLvi1
vi1, 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 and
ec(
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 in
E , 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)
| = 3
n−4. Next we prove that
κ1(
L(
Qn)) = 3
n−4.
Theorem 2
κ1(
L(
Qn)) = 3
n−4, for
n ≥ 4.
Proof First, we verify that
κ1(
L(
Qn))
≤ 3
n−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 | = 3
n−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)
≥ 2
n−2
−4 = 2
n−6
> 1. Then
F is a restricted-vertex-cut. So
κ1(
L(
Qn))
≤ |F | = 3
n−4.
We now show that
κ1(
L(
Qn))
≥ 3
n − 4. By contradiction, suppose that
F is the minimum restricted-
vertex-cut, with
F ⊆ R1,
|F | ≤ 3
n−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 both
G1 and
G2 are connected. Thus
S is a 3-restricted edge cut with
|S| =
|F | ≥ 3
n − 4, it is a contradiction.
Therefore we get that
κ1(
L(
Qn)) = 3
n−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)
| = 4
n−8. Next we proof that
κ2(
L(
Qn)) = 4
n−8.
Theorem 3
κ2(
L(
Qn)) = 4
n−8, for
n ≥ 4.
Proof First, we verify that
κ2(
L(
Qn))
≤ 4
n − 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)
| = 4
n−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))
≤ 4
n − 8.
On the other hand, we show that
κ2(
L(
Qn))
≥ 4
n − 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 | < 4
n − 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| ≥ 4
n − 8, then
|F | =
|S| ≥ 4
n − 8, a contradiction. Therefore,
κ2(
L(
Qn))
≥ 4
n−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
Dr. Mohammad Reza Abbaspour PhD of pharmaceutics Assistant professor Department of Pharmaceutics, School of Pharmacy & Nanotechnology Research Centre Ahvaz Jundishapur University of Medical Sciences P.O. Box: 61357-33184, Ahvaz, Iran Tel / fax: +98 611 3738381 E-mail: abbaspourmr@ajums.ac.ir; abbaspourmr@yahoo.com Education: - Ph.D of pharmaceutics, School of Pharmac
GLI INVESTIMENTI ITALIANI IN ROMANIA Considerando il numero di nuove imprese a partecipazione estera (dati del Registro del Commercio), nel 2012 sono state registrate in Romania 6.384 nuove aziende, portando a 185.791 il numero totale di imprese estere dal 1991. Al 31 dicembre 2012, secondo i dati dell'Ufficio del Registro Nazionale del Commercio, erano registrate complessivamente 34.185 imp