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.

1/--страниц