close

Вход

Забыли?

вход по аккаунту

?

75

код для вставкиСкачать
Tenacity of Complete Graph Products and Grids
S. A. Choudum, N. Priya
Department of Mathematics, Indian Institute of Technology, Madras, Chennai 600 036, India
Received 7 November 1996; accepted 14 December 1998
Abstract: Computer or communication networks are so designed that they do not easily get disrupted
under external attack and, moreover, these are easily reconstructible if they do get disrupted. These
desirable properties of networks can be measured by various parameters like connectivity, toughness,
integrity, and tenacity. In an article by Cozzens et al., the authors defined the tenacity of a graph G(V, E)
as min {uSu 1 t (G 2 S)/ v (G 2 S) : S # V }, where t (G 2 S) and v (G 2 S), respectively, denote the order
of the largest component and number of components in G 2 S. This is a better parameter to measure the
stability of a network G, as it takes into account both the quantity and order of components of the graph
G 2 S. The Cartesian products of graphs like hypercubes, grids, and tori are widely used to design
interconnection networks in multiprocessor computing systems. These considerations motivated us to
study tenacity of Cartesian products of graphs. In this paper, we find the tenacity of Cartesian product of
complete graphs (thus settling a conjecture stated in Cozzens et al.) and grids. © 1999 John Wiley & Sons,
Inc. Networks 34: 192–196, 1999
1. INTRODUCTION
One way of measuring the stability of a network (computer,
communication, or transportation) is through the ease (or
the cost) with which one can disrupt the network. The
connectivity gives the minimum cost to disrupt the network,
but it does not take into account what remains after disruption. One can say that the disruption is more successful if
the disconnected network contains more components and
much more successful if, in addition, the components are
small. As nicely explained in [6] and [8], one can associate
the cost with the number of vertices destroyed to get small
components and associate the reward with the number of
components remaining after destruction. The tenacity measure is a compromise between the cost and the reward by
minimizing the cost:reward ratio. Thus, a network with a
Correspondence to: S. A. Choudum; e-mail: maths1@iitm.ernet.in
© 1999 John Wiley & Sons, Inc.
192
large tenacity performs better under external attack. In this
sense, the following parameters are successively better for
the measurement of stability; see [6] for a comparison.
Before we formally define these parameters, we recall some
standard notation and terminology from [4] and [6].
Let G be a simple graph with vertex set V and edge set
E. For S # V, let v (G 2 S) and t (G 2 S), respectively,
denote the number of components and the order of the
largest component in G 2 S. A set S # V is a cut-set of G,
if either G 2 S is disconnected or G 2 S has only one
vertex.
●
Vertex connectivity:
k~G! 5 min$uSu : S # V is a cut-set of G%;
●
Vertex toughness (Chvátal (1973) [5]):
CCC 0028-3045/99/030192-05
TENACITY OF COMPLETE GRAPH PRODUCTS AND GRIDS
H
t~G! 5 min
●
J
193
5
$~i, ia 2 a 1 1!, . . . , ~i, ia!%
if b 5 0 and 1 # i # m,
$~i, ia 1 i 2 a!, . . . , ~i, ia 1 i!%
Wi 5
if b $ 1 and 1 # i # b,
$~i, ia 1 b 2 a 1 1!, . . . , ~i, ia 1 b!%
if b $ 1 and b 1 1 # i # m,
uSu
: S # V is a cut set of G ;
v ~G 2 S!
Vertex integrity (Barefoot, et al. (1987) [2]):
I~G! 5 min$uSu 1 t ~G 2 S! : S # V%;
ø
m
●
Vertex tenacity (Cozzens et al. (1995) [6]):
H
T~G! 5 min
J
uSu 1 t ~G 2 S!
: S # V is a cut set of G .
v ~G 2 S!
Edge-analogs of these concepts are defined similarly; see [2,
3, 5, 8].
Let G 1 , G 2 , . . . , G r be graphs. The Cartesian product
G 1 3 G 2 3 . . . 3 G r has vertex set V(G 1 ) 3 V(G 2 )
3 . . . 3 V(G r ) with two vertices u 5 ( g 1 , g 2 , . . . , g r )
and v 5 (h 1 , h 2 , . . . , h r ) adjacent iff for exactly one i, g i
Þ h i and ( g i , h i ) is an edge in G i .
As usual, let P n , C n , and K n , respectively, denote the
path, cycle, and complete graph on n vertices. It is well
known that Cartesian products like hypercubes (K 2
3 . . . 3 K 2 ), grids (P n 1 3 . . . 3 P n k), and tori (C n 1
3 . . . 3 C n k) are highly recommended for the design of
interconnection networks in multiprocessor computing systems. Hence, there is a large literature containing the study
of the stability of these graphs; see [1] and [9]. In [6],
among other results, the following theorem and conjecture
are stated:
Theorem A [6]. If m # n, then
m 2 1 mn 2 2m 1 2
# T~K m 3 K n! #
2m
mn 2 n 1
m
n
m
.
Conjecture [6]. If 2 # m # n, then T(Km 3 Kn) 5 (mn 2 n
1 n/m)/m.
In this paper, we prove this conjecture and find the
tenacity of grid graphs Pn1 3 Pn2 3 . . . 3 Pnk.
2. TENACITY OF Km 3 Kn
If S # V(G), the score of S is defined as sc(S) 5 [uSu
1 t (G 2 S)]/[ v (G 2 S)]. Moreover, a set S # V(G) is
called a T-set of G if sc(S) 5 T(G). Let V(K m ) 5 {1,
2, . . . , m}, V(K n ) 5 {1, 2, . . . , n} and V(K m 3 K n )
5 {(i, j) : 1 # i # m, 1 # j # n}. Let n 5 am 1 b,
where 0 # b , m. Define the sets W i as follows:
and let W 5 i51 W i . In [6], the authors showed that
sc(V(K m 3 K n ) 2 W) 5 (mn 2 n 1 n/m)/m and thus
established the upper bound in Theorem A.
Theorem 1. If 1 # m # n, then
mn 2 n 1
T~K m 3 K n! 5
m
n
m
.
Proof. Let G 5 K m 3 K n . For any S # V(G), the
components of G 2 S have the following property:
(1) By the definition of K m 3 K n , the neighborhood of the
vertex (i, j) is {(i, 1), (i, 2), . . . , (i, n)} ø {(1, j),
(2, j), . . . , (m, j)} 2 {(i, j)}. So, if S # V(G) and
(i, j) is a vertex of a component C in G 2 S, then for
every other component D of G 2 S, V(D) ù {(i, 1),
(i, 2), . . . , (i, n)} 5 f and V(D) ù {(1, j), (2,
j), . . . , (m, j)} 5 f . Hence, S contains every vertex
of {(i, 1), (i, 2), . . . , (i, n)} not in V(C) and every
vertex of {(1, j), (2, j), . . . , (m, j)} not in V(C).
Let ^ be the family of all T-sets A in G with the
maximum number of components in G 2 A. Let S be an
element of ^ with minimum order. We shall show that
the components of G 2 S satisfy the following properties (2)–(6) and complete the proof.
(2) Every component C of G 2 S is of the form K s 3 K t .
Let C 1 , C 2 , . . . , C v be the components of G 2 S, with
uV(C i )u 5 m i 3 n i , i 5 1, 2, . . . , v , where v 5 v (G
2 S).
(3) Given any i [ {1, 2, . . . , m} (or j [ {1, 2, . . . , n}),
there exists a component containing some (i, p) [respectively, ( p, j)], where p [ {1, 2, . . . , n} (respectively, p [ {1, 2, . . . , m}).
v
(4) Clearly, by (1), (2), and (3), ¥ i51
m i 5 m and ¥ v
i51 n i
5 n.
(5) For every component C i , either m i 5 1 or n i 5 1.
(6) There is no component with m i . 1 and n i 5 1.
Thus, all the components are of the form K 1 3 K n i, uV(C i )u
5 n i , v (G 2 S) 5 m, uSu 5 mn 2 ¥ m
i51 n i 5 mn 2 n,
and t (G 2 S) $ n/m. We thus get the required lower
bound:
194
CHOUDUM AND PRIYA
uSu 1 t ~G 2 S!
T~G! 5
$
v ~G 2 S!
mn 2 n 1
n
m
m
Adding the two inequalities, we get uSu 1 t (G 2 S)
$ v (G 2 S)(s 1 t 2 2). So,
.
Proof of (2). It is enough if we show that whenever (i,
r), (i, s), ( j, r) [ V(C) then ( j, s) [ V(C). On the
contrary, suppose that ( j, s) ¸ V(C). Define S9 5 S 2 ( j,
s). By (1), ( j, s) [ S, ( j, s) is adjacent with (i, s), ( j, r)
in G 2 S9 and [C ø {( j, s)}] is a component of G 2 S9,
so uS9u 5 uSu 2 1, v (G 2 S9) 5 v (G 2 S), t (G 2 S9)
# t (G 2 S) 1 1. Hence,
sc~S9! 5
uS9u 1 t ~G 2 S9!
v ~G 2 S9!
#
sc~S9! 5
uS9u 1 t ~G 2 S9!
v ~G 2 S9!
#
uSu 1 t ~G 2 S! 1 ~s 1 t 2 2!
v ~G 2 S! 1 1
#
uSu 1 t ~G 2 S!
v ~G 2 S!
~since ~s 1 t 2 2! v ~G 2 S! # uSu 1 t ~G 2 S!!
uSu 2 1 1 t ~G 2 S! 1 1
5 sc~S!
v ~G 2 S!
and so S9 is a T-set. But this contradicts the fact that uSu is
of minimum order.
Proof of (3). Assume the contrary; so, S $ {(i, j) : 1
# j # n} for some i, 1 # i # m. Let C be a component
of G 2 S and (k, r) be an element of C. Define S9 5 S
2 (i, r). Then, [C ø {(i, r)}] is a component in G 2 S9,
uS9u 5 uSu 2 1, t (G 2 S9) # t (G 2 S) 1 1, and v (G
2 S9) 5 v (G 2 S). Hence, S9 is a T-set as above,
contradicting the fact that S is of minimum order.
Proof of (5). Assume that there is a component C i 5 K m i
3 K n i with m i . 1 and n i . 1. For notational convenience,
let m i 5 s, n i 5 t. Without loss of generality, assume that
C 1 5 K s 3 K t , where V(K s ) 5 {1, 2, . . . , s} and V(K t )
5 {1, 2, . . . , t}. Let S9 5 S ø {(s, 1), (s, 2), . . . , (s,
t 2 1)} ø {(1, t), (2, t), . . . , (s 2 1, t)}. Then, uS9u
5 uSu 1 s 1 t 2 2, and the components of G 2 S9 are
C 2 , . . . , C v [where v 5 v (G 2 S)], a singleton component containing the vertex (s, t) and a component [(V(K s )
2 {s}) 3 (V(K t ) 2 {t})] , C 1 . So, t (G 2 S9) # t (G
2 S) and v (G 2 S9) 5 v (G 2 S) 1 1. We now estimate
the size of S. Let [ x, y] denote the set of all integers z, such
that x # z # y. Since C 1 is a component in G 2 S, S
$ [1, s] 3 [t 1 1, n] ø [s 1 1, m] 3 [1, t]. So,
5 sc~S!.
Hence, S9 is a T-set with v (G 2 S9) . v (G 2 S), which
is a contradiction to the choice of S.
Proof of (6). We first observe that if there is a component C i 5 K m i 3 K 1 with m i . 1 then there is a component
C j 5 K 1 3 K n j with n j . 1; otherwise, n j 5 1 for every
j, and we have the contradiction: v 1 1 # ¥ v
i51 m i 5 m
# n 5 ¥v
n
5
v
.
j51 j
To prove (6), assume on the contrary that there is a
component C 5 K s 3 K 1 with s . 1. By the above
observation, there is a component D 5 K 1 3 K t with t
. 1. Without loss of generality, assume that V(C) 5 {(1,
a), (2, a), . . . , (s, a)} and V(D) 5 {(b, 1), (b, 2), . . . ,
(b, t)}, where b ¸ {1, 2, . . . , s} and a ¸ {1, 2, . . . , t}.
Define S9 5 S ø {(s, a)} ø {(b, t)} 2 {(s, t)}. Then,
uS9u 5 uSu 1 1, v (G 2 S9) 5 v (G 2 S) 1 1 with the new
extra component being the singleton {(s, t)}, and t (G
2 S9) # t (G 2 S). We next estimate the size of S. Since
C 5 K s 3 K 1 (5C k (say)) is a component of G 2 S, S
. {(s 1 1, a), (s 1 2, a), . . . , (m, a)}. So, uSu $ m
v
2 s 5 ¥ j51,
jÞk m j $ v (G 2 S) 2 1. Since t (G 2 S)
. 1, we get uSu 1 t (G 2 S) . v (G 2 S). But, then,
sc~S9! 5
uSu $ s~n 2 t! 1 ~m 2 s!t
5 s~n 2 1 n 3 1 · · · 1 n v! 1 ~m 2 1 m 3 1 · · · 1 m v!t
O n 5 t 1 O n 5 n and O m 5 s 1 O m 5 m,
v
since
v
i
i51
v
i
i52
v
i
i51
i
uS9u 1 t ~G 2 S9!
v ~G 2 S9!
#
uSu 1 1 1 t ~G 2 S!
v ~G 2 S! 1 1
,
uSu 1 t ~G 2 S!
v ~G 2 S!
i52
$ s~ v 2 1! 1 ~ v 2 1!t
5 ~ v 2 1!~s 1 t!
Next, t (G 2 S) $ uC 1 u 5 st $ s 1 t 2 2 $ s 1 t
2 2v.
~since uSu 1 t ~G 2 S! . v ~G 2 S!!
5 sc~S!.
We thus have a contradiction to the minimality of
sc(S).
■
TENACITY OF COMPLETE GRAPH PRODUCTS AND GRIDS
3. TENACITY OF GRIDS Pn1 3 Pn2 3 . . .
3 Pnk
To find the tenacity of grids, we require the tenacity of
complete bipartite graph K m,n and paths.
Theorem B [6]. If 1 # m # n, then T(Km,n) 5 (m 1 1)/n.
Next, if P n 2 S contains two K 2 components, say (i, i
1 1) and ( j, j 1 1), where j $ i 1 3, assume, without
loss of generality, that P n 2 S has no edges (r, r 1 1),
where i 1 3 # r # j 2 3. Clearly, i 1 2, j 2 1 [ S.
Let S9 5 S ø {i 1 1, i 1 3, . . . , j 2 2} ø { j}
2 {i 1 2, i 1 4, . . . , j 2 1}. Then, uS9u # uSu 1 1,
t (P n 2 S9) # t (P n 2 S), v (P n 2 S9) $ v (P n 2 S)
1 1, and
Theorem 2. For every integer n $ 2,
H
sc~S9! 5
1
if n is odd,
n
1
2
T~P n! 5
if n is even.
n
Proof. At the outset, we observe that v (P n 2 S) # uSu
1 1, for every S # V(P n ). Let 1, 2, . . . , n be the vertices
and (i, i 1 1) be the edges of P n . Clearly, if H is a spanning
subgraph of G, then T(H) # T(G). Since,
Pn #
5
Kn21
2
,
n11
2
Kn n
,
2 2
H
if n is odd,
if n is even,
#
#
uSu 1 1 1 t ~P n 2 S!
v ~P n 2 S! 1 1
,
uSu 1 t ~P n 2 S!
v ~P n 2 S!
5 sc~S!,
again a contradiction to the minimality of sc~S!.
We next complete the proof by taking a T-set S of P n and
distinguishing two cases:
if n is odd,
if n is even.
To establish the lower bound, we first claim that if S is a
T-set of P n , then (i) every component of P n 2 S is K 1 or
K 2 , and (ii) there is at most one K 2 component. We assume
the contrary and arrive at a contradiction. If P n 2 S
contains a component P k 5 {i 1 1, i 1 2, . . . , i 1 k},
where k $ 3, then defining S9 5 S ø {i 1 2}, we have
uS9u 5 uSu 1 1, t (P n 2 S9) # t (P n 2 S), v (P n 2 S9)
5 v (P n 2 S) 1 1, and
sc~S9! 5
uS9u 1 t ~P n 2 S9!
v ~P n 2 S9!
~since uSu 1 t ~P n 2 S! . v ~P n 2 S!!
it follows by Theorem B, that
1
T~P n! # n 1 2
n
195
uS9u 1 t ~P n 2 S9!
v ~P n 2 S9!
uSu 1 1 1 t ~P n 2 S!
v ~P n 2 S! 1 1
uSu 1 t ~P n 2 S!
,
v ~P n 2 S!
~since uSu 1 t ~P n 2 S! $ v ~P n 2 S! 1 2!
5 sc~S!, a contradiction to the minimality of sc~S!.
CASE 1. t (P n 2 S) 5 1.
Clearly, uSu $ n/ 2, and v (P n 2 S) # n/ 2.
Hence,
T~P n! 5 sc~S! 5
uSu 1 t ~P n 2 S!
v ~P n 2 S!
H
n
1
11
2
$
5 n12
n
n
2
if n is odd,
if n is even.
CASE 2. t (P n 2 S) 5 2.
Clearly, uSu $ (n 2 2)/ 2, and v (P n 2 S) # n/
2. Hence,
T~P n! 5
uSu 1 t ~P n 2 S!
v ~P n 2 S!
H
n22
1
12
2
$
5 n12
n
n
2
if n is odd,
■
if n is even.
Theorem 2 was also proved by Mann [7]. We thank one
of the referees for this reference and asking us to retain our
simple proof.
196
CHOUDUM AND PRIYA
T~P n1 3 P n2 3 . . . 3 P nk!
Before proving our next theorem, we make a simple
observation: If a graph G contains a Hamilton path, then so
does G 3 P n .
H
1
# n 1n 2 . . . n k 1 2
n 1n 2 . . . n k
Theorem 3. For all positive integers n1, n2, . . . , nk,
H
if all n i are odd,
if some n i is even.
Proof. By the above observation, it follows that P n 1
3 P n 2 3 . . . 3 P n k contains a Hamilton path P n 1n 2. . .n k. So,
by Theorem 2,
T~P n1 3 P n2 3 . . . 3 P nk! $ T~P n1n2 . . . nk!
H
1
5 n 1n 2 . . . n k 1 2
n 1n 2 . . . n k
if some n i is even.
If G is a bipartite graph with bipartition [A, B] and H is
a bipartite graph with bipartition [C, D], then it is well
known that G 3 H is a bipartite graph with bipartition
[( A 3 C) ø (B 3 D), ( A 3 D) ø (B 3 C)]. Hence,
it follows that
REFERENCES
[2]
[3]
[4]
[5]
[6]
P n1 3 P n2 3 . . . 3 P nk
5
K n1n2 . . . nk21, n1n2 . . . nk11
2
2
if all n i are odd,
# K n1n2 . . . nk n1n2 . . . nk
,
2
2
[7]
[8]
if some n i is even.
[9]
So, by Theorem B, we get
■
Corollary 3.1. For every positive integer n, T(Qn) 5 (2n
1 2)/2n.
■
[1]
if all n i are odd,
if some n i is even.
Since a hypercube Q n is the Cartesian product P 2 3 P 2
3 . . . 3 P 2 (n times), we have the following corollary,
a result also proved by Stuart (see [6]).
T~P n1 3 P n2 3 . . . 3 P nk!
1
5 n 1n 2 . . . n k 1 2
n 1n 2 . . . n k
if all n i are odd,
G. Almasi and A. Gottlieb, Highly parallel computing, Benjamin/Cummings, Redwood City, CA, 1989.
C.A. Barefoot, R. Entringer, and H. Swart, Integrity of trees
and powers of cycles, Cong Num 58 (1987), 103–114.
C.A. Barefoot, R. Entringer, and H. Swart, Vulnerability in
graphs: A comparative survey, J Combin Math Combin Comput 1 (1987), 13–22.
J.A. Bondy and U.S.R. Murty, Graph theory and applications,
Macmillan, London, 1976.
V. Chvátal, Tough graphs and Hamiltonian circuits, Discr
Math 5 (1973), 215–228.
M. Cozzens, D. Moazzami, and S. Stueckle, “The tenacity of
a graph,” Proc Seventh International Conf on the Theory and
Applications of Graphs, Wiley, New York, 1995, pp. 1111–
1122.
D.E. Mann, The tenacity of trees, Ph.D. Thesis, Northeastern
University, 1993.
B.L. Piazza, F.S. Roberts, and S.K. Stueckle, Edge tenacious
networks, Networks 25 (1995), 7–17.
M.J. Quinn, Parallel computing: Theory and practice,
McGraw-Hill, New York, 1994.
Документ
Категория
Без категории
Просмотров
18
Размер файла
73 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа