Uniformly Optimally Reliable Graphs D. Gross, J. T. Saccoman Department of Mathematics and Computer Science, College of Arts and Sciences, Seton Hall University, South Orange, New Jersey 07079-2696 Received 28 October 1997; accepted 17 December 1997 Abstract: A graph with n nodes and e edges, where the nodes are perfectly reliable and the edges fail independently with equal probability r, is said to be uniformly optimally reliable (UOR) if it has the greatest reliability among all graphs with the same number of nodes and edges for all values of r. UOR simple graphs have been identified in the classes e Å n 0 1, e Å n, e Å n / 1, and e Å n / 2 (Boesch et al., Networks 21 (199) 181–194). In this paper, we demonstrate that the UOR simple graphs in these classes are also UOR when the classes are extended to include multigraphs. q 1998 John Wiley & Sons, Inc. Networks 31: 217–225, 1998 1. INTRODUCTION AND PRELIMINARIES Let G Å »V (G), E(G) … denote a graph with node set V (G) Å { £1 , £2 , . . . , £n } and edge set E(G) Å {x1 , x2 , . . . , xe }. We allow there to be more than one edge between a pair of nodes; if this occurs, we refer to each of them as a multiple edge. A double edge consists of two multiple edges and a triple edge consists of three multiple edges. If there is only one edge between a pair of nodes, it is called a simple edge. The term edge will subsume both a simple edge and a multiple edge. We use the term multigraph to refer to a graph that contains at least one multiple edge but no loops and the term simple graph to refer to a graph with neither multiple edges nor loops. Let V(n, e) denote the class of all graphs (simple graphs or multigraphs) with n nodes and e edges, and Vs (n, e), the class of all simple graphs with n nodes and e edges. For other standard graph-theoretic notation and terminology, we refer to Harary [3]. If the graph represents a connected network, we can discuss a model in which nodes are perfectly reliable and Correspondence to: D. Gross edges fail independently with equal probability r, 0 õ r õ 1. We define the so-called unreliability polynomial, e P(G, r ) Å ( iÅ1 mi r i (1 0 r ) e0i , where mi is the number of edge-disconnecting sets of size i. The reliability of a graph, therefore, can be defined as R(G, r ) Å 1 0 P(G, r ). A graph G is said to be uniformly optimally reliable (UOR) if for each H in its class P(G, r ) ° P(H, r ) [respectively, R(G, r ) ¢ R(H, r )] for all 0 õ r õ 1. Because P(G, r ) Å 1 whenever G is disconnected, it suffices to consider only connected graphs. It is obvious that if a graph minimizes each term mi among all graphs in its class then it will have the smallest value of P in its class for all r and, consequently, the largest value of R. Hence, it is UOR. While all known examples of UOR graphs would indicate that the converse is true, a proof of this fact has yet to be found. In the 1991 paper ‘‘On the Existence of Uniformly Optimally Reliable Networks,’’ Boesch et al. demonstrated the existence of UOR simple graphs in the classes Vs (n, n 0 1), Vs (n, n), Vs (n, n / 1), and Vs (n, n / 2) by finding simple graphs that minimize mi for all i [1]. Wang covered the class Vs (n, n / 3) [5]. Let G 0 x denote the deletion of an edge x from the graph G, and G/x, the contraction of the edge x, that is, q 1998 John Wiley & Sons, Inc. CCC 0028-3045/98/040217-09 217 8U1F / 8U1F$$0815 05-14-98 08:07:51 netwa W: Networks 0815 218 GROSS AND SACCOMAN the identification of the endnodes of x and the deletion of all resulting self-loops. The following theorem, which is credited to Moskowitz [4], applies to many graph invariants. It is stated here in terms of the number of edgedisconnecting sets: Theorem 1.1. (Factoring Theorem) Suppose that G is a connected graph and x is a simple edge in G. For all i, 1 ° i ° e, mi (G) Å mi01 (G 0 x) / mi (G/x). The Factoring Theorem does not apply to factoring on a multiple edge, since contraction of a multiple edge would result in a graph having more than one fewer edge than the original graph. If the class of graphs under consideration was extended to include pseudographs, that is, both multiple edges and loops are allowed, and the definition of contraction was amended so that only the loop formed by the actual edge contracted was deleted, then the Factoring Theorem would hold. Henceforth, any factoring performed is on simple edges in the graph. In the first proposition, we show that the placement of a bridge in a graph has no bearing on mi : Proposition 1. Let G be a graph with a bridge x, and G * be the graph obtained by contracting the bridge x and adding a pendent edge y. Then, mi (G) Å mi (G * ) for all i, 1 ° i ° e. (See Fig. 1 for an illustration.) Proof. Factor on the bridge x and the pendent edge y in the respective graphs G and G *. Since G/x and G * /y are isomorphic, mi (G/x) Å mi (G * /y) for all i. The deletion graphs G 0 x and G * 0 y are disconnected, so mi01 (G 1 0 x) Å mi01 (G * 0 y) Å ( e0 i01 ) for all i. Thus, mi01 (G 0 x) / mi (G/x) Å mi01 (G * 0 y) / mi (G * /y), i.e., mi (G) Å mi (G * ) for all i. Next, we establish that a graph containing a cycle and a pendent edge will have mi at least as large as that of a graph in the same class having a longer cycle and one fewer pendent edge. Proposition 2. Let G be a nonacyclic graph with a pendent edge x and let G * be the graph obtained by contracting the pendent edge x and subdividing a cycle edge Fig. 2. mi (G) ¢ mi (G*); m1 (G) ú m1 (G*). into two edges. Then, mi (G) ¢ mi (G * ) for all i, 2 ° i ° e, and m1 (G) ú m1 (G * ). (See Fig. 2 for an illustration.) Proof. Let y be one of the edges formed in the subdivision. We factor on x in G and y in G *. Since G/x and G * /y are isomorphic, mi (G/x) Å mi (G * /y) for all i. 1 Since G 0 x is disconnected, mi (G 0 x) Å ( e0 i01 ) for all i. On the other hand, G * 0 y is connected, which implies that there may be some choices of the remaining edges 1 which do not disconnect. Thus, mi01 (G * 0 y) ° ( e0 i01 ) for all i, and mi (G) Å mi01 (G/x) / mi (G/x) ¢ mi01 (G * 0 y) / mi (G * /y) Å mi (G * ). Since m1 (G) is the number of bridges, and G * has one fewer bridge than has G, m1 (G) ú m1 (G * ). Repeated application of Propositions 1 and 2 imply that, given any graph G having a bridge, there exists a bridgeless graph G * in the same class such that P(G *, r ) õ P(G, r ), for all 0 õ r õ 1. The following is an immediate consequence: Proposition 3. If there exists a bridgeless graph G in the class V(n, e) such that P(G, r) ° P(H, r) for all bridgeless graphs H in the class V(n, e) and for all r, 0 õ r õ 1, then G is UOR. 2. THE CLASSES V(n, n 0 1) AND V(n, n) There are no connected multigraphs in the class V(n, n 0 1). Any connected simple graph is a tree, all of which have mi Å ( n0i 1 ), i ¢ 1. Thus, all connected graphs in V(n, n 0 1) are UOR. There are no connected bridgeless multigraphs in the class V(n, n). The only connected bridgeless simple graph in this class is Cn , the cycle on n nodes. Thus, Cn is the unique UOR graph in the class V(n, n). 3. THE CLASS V(n, n / 1) Fig. 1. mi (G) Å mi (G*). 8U1F / 8U1F$$0815 05-14-98 08:07:51 The removal of three or more edges from any graph in the class V(n, n / 1) always results in a disconnected netwa W: Networks 0815 UNIFORMLY OPTIMALLY RELIABLE GRAPHS 219 1 graph; hence, mi Å ( n/ ) for any graph in the class and i for all i ¢ 3. Thus, the only value that differentiates one bridgeless graph from another is m2 . The unique UOR simple graph in the class Vs (n, n / 1) is obtained in the following manner [1]: STEP 1. Start with a triple-edge between two isolated nodes u and £. STEP 2. Distribute n 0 2 nodes as equally as possible among the three edges. (See Fig. 3 for an illustration.) We refer to each of the three resulting paths joining u to £ as an edge-path. The only way to disconnect a UOR simple graph by the removal of two edges is by deleting two of the edges along an edge-path. If there are j internal points on one of these edge-paths, then the number of ways to disconnect in this fashion is ( 2j / 1 ). These edge-paths are subdivided as evenly as possible, so if k Å (n 0 2) mod 3, then k of the edge-paths have (n 0 2)/3 internal nodes, while the other 3 0 k will have (n 0 2)/3 internal nodes. These observations are summarized in the following theorem: Fig. 3. UOR graph in Vs (7, 8). k Å 2: m2 Å n04 /1 3 2 /2 n01 /1 3 2 Theorem 3.1. The UOR simple graphs in the class Vs (n, n / 1) have m2 n02 3 Å (3 0 k) /1 /k n02 3 2 /1 , 2 n(n 0 1) . 6 By Proposition 3, we only need to compare the UOR simple graph to the bridgeless multigraphs in this class. To see that there are only two such multigraphs, namely, H1 , the cycle on n nodes with one of its edges doubled, and H2 , the cycle on n 0 1 nodes with a pendent double edge (see Fig. 4 for an illustration), we need only consider the graphs that result from the deletion of one of 1 1 ) õ ( n0 )/1 the multiple edges. Since m2 (H1 ) Å ( n0 2 2 Å m2 (H2 ), H1 is the best multigraph, so it is only necessary to compare it to the UOR simple graph. Indeed, for k Å 0: m2 (H1 ) 0 m2 (UOR) Å where k Å (n 0 2) mod 3. Specifically, Å (n 0 2) 2 ú 0, 3 when n ú 2; k Å 0: m2 Å 3 n02 /1 3 Å 2 k Å 1: m2 Å 2 (n / 1)(n 0 2) . 6 k Å 1, 2: m2 (H1 ) 0 m2 (UOR) Å (n 0 3)(n 0 1) ú 0, 3 when n ú 3. Thus, the graph in Vs (n, n / 1) which is UOR among all simple graphs remains UOR when we extend the class to include multigraphs. n03 /1 3 2 4. THE CLASS V(n, n / 2) / n /1 3 2 8U1F / 8U1F$$0815 Å n(n 0 1) . 6 05-14-98 08:07:51 The removal of four or more edges from any graph in the class, V(n, n / 2) always results in a disconnected graph, so mi Å ( n/i 2 ) for any graph in the class and for netwa W: Networks 0815 220 GROSS AND SACCOMAN m2 Å (6 0 k) n04 /1 6 /k n04 /1 6 , 2 2 specifically as follows: k Å 0: m2 Å 6 n/2 6 n 2 0 2n 0 8 . 12 Å 2 Fig. 4. Multigraphs in V(7, 8). k Å 1: m2 Å 5 all i ¢ 4. Thus, the only values that differentiate one bridgeless graph from another are m2 and m3 . The unique UOR simple graph in the class Vs (n, n / 2), n ¢ 4, is obtained in the following manner [1]: Theorem 4.1. Let k Å (n 0 4) mod 6. (i) The UOR simple graph in the class Vs (n, n / 2) has 8U1F / 8U1F$$0815 05-14-98 08:07:51 n/7 6 / 2 2 Å STEP 1. Start with the graph K4 , the complete graph on 4 nodes. STEP 2. Distribute n 0 4 nodes among the six edges as follows: Let k Å (n 0 4) mod 6. If k Å 0, 1, 5 distribute the n 0 4 nodes among the six edges of the K4 as evenly as possible; If k Å 2, i.e., n 0 4 Å 6m / 2, insert m nodes in each of the six edges of the K4 and the two remaining nodes in two independent edges (of the original K4 ); If k Å 4, i.e., n 0 4 Å 6m / 4, insert m / 1 nodes in each of the six edges of the K4 and then remove two nodes from a pair of independent edges (of the original K4 ); If k Å 3, i.e., n 0 4 Å 6m / 3, insert m nodes in each of the six edges of the K4 two of the remaining nodes in two independent edges (of the original K4 ), and the last node in any one of the remaining four edges (of the original K4 ). (See Fig. 5 for an illustration.) We refer to the six paths joining the endnodes of the original edges of the K4 as edge-paths. The only way to disconnect a UOR simple graph by the removal of two edges is to delete two of the edges on an edge-path. On the other hand, there are three different ways to disconnect by removing three edges: removing three edges from one edge-path; removing two from one edge-path and one from a different edge-path; or removing exactly one edge from each of the three edge-paths emanating from an original node of the K4 . The number of ways each can be done depends on how the n 0 4 nodes are inserted in the six edges of K4 and is summarized in the following theorem: n/1 6 k Å 2: m2 Å 4 n 6 /2 n/6 6 2 k Å 3: m2 Å 3 Å 2 n01 6 /3 2 Å n02 6 n 2 0 2n . 12 n/5 6 2 k Å 4: m2 Å 2 n 2 0 2n 0 3 . 12 /4 n 2 0 2n / 1 . 12 n/4 6 2 2 Å k Å 5: m2 Å n03 6 2 /5 n 2 0 2n . 12 n/3 6 2 Å n 2 0 2n 0 3 . 12 (ii) The UOR simple graph in the class Vs (n, n / 2) has m3 Å a / b / c, where a is the number of ways to remove three edges from one edge-path, b is the number of ways to remove two edges from one edgepath and one edge from a different edge-path, and c is the number of ways to remove exactly one edge from each of the three edge-paths emanating from an original K4 node. The following chart summarizes this information for m3 : netwa W: Networks 0815 UNIFORMLY OPTIMALLY RELIABLE GRAPHS a b 6 n/2 6 5 n/1 6 kÅ2 4 n 6 3 3 2 kÅ3 n01 6 3 n/5 6 /3 n01 6 3 kÅ4 n02 6 2 kÅ0 6 n/2 6 5 n/1 6 4 n 6 3 kÅ1 / 3 3 /2 3 3 3 kÅ5 n03 6 /5 2 n/3 6 n03 6 3 2 3 G 5n / 12 /2 6 n02 6 2 3 G F 2 n/4 6 /4 F 5n 3 / 3n 2 0 30n 0 32 54 k Å 1: 5n 3 / 3n 2 0 18n 0 16 54 3 n/7 6 F G F G F G 2 n/6 6 2 n/5 5n / 13 6 /3 6 2 5n / 14 /4 6 5n / 15 /5 6 The values of a / b / c are as follows: k Å 0: 4 5n / 11 / 6 2 n/6 6 G c 5n / 10 6 2 n/7 6 F n/4 6 2 n/3 6 2 5n / 3n 0 18n 54 k Å 3: 5n 3 / 3n 2 0 12n / 4 54 k Å 4: 5n 3 / 3n 2 0 18n 0 16 54 k Å 5: 5n 3 / 3n 2 0 36n . 54 F G 2 G 4 5n / 6 6 G 2 F 5n / 8 6 G 4 F G 2 5n / 9 6 3 n/1 6 2 n/7 n/1 /2 6 6 3 F GF G F 5n / 7 6 n/2 6 F GF G F G 5n / 5 6 F F G n 6 2 n/6 6 F G F G F GF G n01 6 2 n/5 n01 /2 6 6 n/5 6 2 F GF G n02 6 n/4 6 2 F G F G F GF G n03 6 2 n/3 n03 /2 6 6 n/3 6 2 nonnegative integers. If s 0 r Å k ú 0, then f (r, s) 0 f (r / 1, s 0 1) Å k 0 1. Proposition 6. Let n be a fixed positive integer, and let r and s be nonnegative integers. Then, (i) The expression ( r2 ) / ( n0r 2 ) is minimized when r Å n/2 . (ii) The expression ( r2 ) / ( s2 ) / ( n0r20s ) is minimized when r Å n/3 and s Å n/3 . 2 k Å 2: 221 Corollary 4. Let G be the UOR simple graph in Vs (n, n / 2). Then, m2 (G) ° (n 2 0 2n / 1)/12 and m3 (G) ° (5n 3 / 3n 2 0 12n / 4)/54. There are four types of constructions that give bridgeless multigraphs in the class V(n, n / 2). Proposition 6, which follows below, enables us to find the most reliable multigraph within each type. We first state a lemma which is used in the proof of the proposition: Lemma 5. Let f (r, s) Å ( r2 ) / ( s2 ), where r and s are 8U1F / 8U1F$$0815 05-14-98 08:07:51 Fig. 5. UOR graphs in Vs (n, n / 2), n Å 10, 11, . . . , 15. The large nodes are the k additional nodes. netwa W: Networks 0815 222 GROSS AND SACCOMAN Fig. 6. Type1 multigraphs in V(7, 9). (iii) The expression ( r2 ) / ( n0r 2 ) / r/2 is minimized when r Å n/2 . (i£ ) The expression ( r2 ) / ( s2 ) / ( n0r20s ) / r/2 is minimized when r Å n/3 and s Å n/3 . Proof. Parts (i) and (ii) are well known and the proof of (iv) is similar to that of (iii), so we only give the proof of (iii). (iii) Let s Å n 0 r, and define the function F(r, s) Å f (r, s) / r/2, where f (r, s) is as defined in Lemma 5. Trivially F(r, s) ° F(s, r), whenever r ° s, so without loss of generality, we assume that r ° s. Assume that F(r, s) is minimized and r õ n/2 . Then, since r / s Å n, s ú n/2 . Thus, s 0 r ¢ 2. Lemma 5 implies that f (r, s) 0 f (r / 1, s 0 1) ¢ 1. Hence, F(r, s) 0 F(r / 1, s 0 1) Å ( f (r, s) / (r/2)) 0 ( f (r / 1, s 0 1) / (r / 1)/2) ¢ 12, which contradicts the assumption that F(r, s) is minimized. Therefore, r Å n/2 . Next, we describe the four constructions leading to bridgeless multigraphs in V(n, n / 2). For each construction type, we determine the best multigraph, then find the best one from among the four, and finally compare the best multigraph to the UOR simple graph in V(n, n / 2). A multigraph is of Type1 if it is constructed in the following manner: binatorial formulas for m2 and m3 , if in Step 2 of the construction an original edge was not subdivided, then if this edge was the one doubled in Step 3, it will be considered an edge-path consisting of two multiple edges which form a double edge; otherwise, the unsubdivided edge is considered an edge-path consisting of a single simple edge. Let r be the number of simple edges on the edgepath containing the double-edge; s, the number of simple edges on a second edge-path; and n 0 r 0 s, the number of simple edges on the third edge-path. The only way to disconnect a Type1 multigraph by the removal of two edges is to remove two simple edges from the same edge-path. Thus, m2 Å ( r2 ) / ( s2 ) / ( n0r20s ). By part (ii) of Proposition 6, we know that m2 is minimized when r Å n/3 and s Å n/3 , i.e., the number of simple edges on each edge-path is as equal as possible. There are three ways to disconnect by removing three edges: remove any three simple edges; remove two simple edges from the same edge-path and one of the multiple edges from the double-edge; or remove the double-edge and a simple edge from the edge-path that contained the double-edge. Hence, m3 Å ( n3 ) / 2(( r2 ) / ( s2 ) / ( n0r0s 2 )) / r. Since the first summand is constant for all graphs of Type1, applying part (iv) of Proposition 6 yields that m3 is also minimized when r Å n/3 and s Å n/3 . Thus, the best graph of this type, which we call M1 , is constructed as follows: Begin with three edges between a pair of nodes and distribute n 0 2 nodes as evenly as possible among the three edges. Next double an edge on an edge-path that has the most nodes. The values of m2 and m3 depend on the value of k Å n mod 3. Specifically, n k Å 0: m2 Å 3 3 Å 2 SD n m3 Å 3 STEP 1. Start with a three edges between a pair of nodes. n 3 /6 8U1F / 8U1F$$0815 05-14-98 08:07:51 / 2 STEP 2. Insert n 0 2 nodes randomly in the three edges. STEP 3. Double one of the edges. Type1 multigraphs include M2 : the n-cycle with one edge tripled (i.e., insert the nodes into only one edge and double one of the original edges); M3 : the n-cycle with two edges doubled (i.e., insert the nodes into only one edge and double one of the newly-formed edges); M4 : the chordal n-cycle with a double-edge on the cycle (i.e., insert the nodes into two of the original edges and double one of the newly formed edges); and M5 : the n-cycle with a double chord (i.e., insert the nodes into two of the original edges and double the other original edge). (See Fig. 6 for an illustration.) We refer to the resulting paths between the original two nodes as edge-paths. For ease of describing the com- n 2 0 3n , 6 n01 3 k Å 1: m2 Å 2 / n/2 3 2 m3 Å k Å 2: m2 Å netwa SD n 3 / 2m2 / n02 3 SD n 3 W: Networks Å 2 2 / 2m2 / 0815 n 2 0 3n / 2 , 6 n 0 1 n 3 0 n 2 0 2n / 2 Å ; 3 6 n/1 3 /2 2 m3 Å n n 3 0 n 2 0 2n Å ; 3 6 Å n 2 0 3n / 2 , 6 n 0 2 n 3 0 n 2 0 2n Å . 3 6 UNIFORMLY OPTIMALLY RELIABLE GRAPHS 223 the three edges. The pendent double edge may be added anywhere. It follows immediately from the discussion above that m2 (M6 ) 0 m2 (M1 ) Å 1, and m3 (M6 ) 0 m3 (M1 ) Å n 0 r ú 0. Therefore, M1 is the best multigraph among all multigraphs of Type1 or Type2. A multigraph is of Type3 if it is constructed in the following manner: STEP 1. Start with a path of length 2. STEP 2. Double each edge. Fig. 7. Type2 multigraphs in V(7, 9). STEP 3. Insert n 0 3 nodes randomly in the double edges. Thus, for any value of n, we obtain (n 2 0 3n)/6 ° m2 (M1 ) ° (n 2 0 3n / 2)/6 and (n 3 0 n 2 0 2n)/6 ° m3 (M1 ) ° (n 3 0 n 2 0 2n / 2)/6. A multigraph is of Type2 if it is constructed in the following manner: STEP 1. Start with three edges between a pair of nodes. STEP 2. Insert n 0 3 nodes randomly in the three edges so that at least two of the edges receive nodes. STEP 3. Connect a new node to any other node using two edges, forming a pendent double edge. If only two of the original three edges are subdivided, the resultant multigraph, M7 , is a chordal (n 0 1)-cycle with a pendent double edge. (See Fig. 7 for an illustration.) We refer to the three paths between the original two nodes as edge-paths. For ease of describing the combinatorial formulas for m2 and m3 , if in the construction one of the original three edges is not subdivided, it will be considered an edge-path consisting of a single simple edge. Let r be the number of simple edges on the edgepath containing the double edge; s, the number of simple edges on a second edge-path; and, therefore, n 0 r 0 s, the number of simple edges on the third edge-path. There are two ways to disconnect a Type2 multigraph by the removal of two edges: remove two simple edges from the same edge-path or remove the pendent double 0s edge. Thus, m2 Å ( r2 ) / ( s2 ) / ( n0r ) / 1. Again, by part 2 (ii) of Proposition 6, m2 is minimized when r Å n/3 and s Å n/3 , that is, the n 0 3 nodes should be inserted as evenly as possible along the edge paths. There are three ways to disconnect by a Type2 multigraph by the removal of three edges: remove any three simple edges, remove two simple edges from the same edge-path and one of the multiple edges, or remove the pendent double edge and any other edge. Hence, m3 0s Å ( n3 ) / 2(( r2 ) / ( s2 ) / ( n0r )) / n. Once again, m3 is 2 minimized when r Å n/3 and s Å n/3 . Thus, the best graph of this type, M6 , is constructed as follows: Start with three edges between a pair of nodes and distribute n 0 3 nodes as evenly as possible among 8U1F / 8U1F$$0815 05-14-98 08:07:51 STEP 4. Double an edge. If the nodes are inserted in both of the double edges formed in Step 2, the resulting multigraph, M8 , is a bicycle (i.e., two cycles with a common node) with one double edge. If the nodes were inserted in only one of the double edges formed in Step 2, then if one of the multiple edges from the other double edge was the one doubled in Step 4, we obtain M9 , an (n 0 1)-cycle with a pendent triple edge; otherwise, the graph obtained, M10 , is an (n 0 1)cycle with one edge doubled and a pendent double edge. (See Fig. 8 for an illustration.) For ease of describing the combinatorial formulas for m2 and m3 , if the multigraph has a pendent double edge, we treat it as a cycle consisting of two simple edges, and if the multigraph has a pendent triple edge, we consider it to be a cycle of length 2 with one double edge and one simple edge. Let r be the number of simple edges on the cycle containing the double edge; then, n 0 r is the number of simple edges on the other cycle. The only way to disconnect a Type3 multigraph by the removal of two edges is to remove two simple edges on one of the cycles. Thus, m2 Å ( r2 ) / ( n0r 2 ). By part (i) of Proposition 6, m2 is minimized when r Å n/2 . There are three ways to disconnect a Type3 multigraph by removing three edges: remove any three simple edges, remove two simple edges from the same cycle and a netwa Fig. 8. Type3 multigraphs in V(7, 9). W: Networks 0815 224 GROSS AND SACCOMAN multiple edge, or remove the double edge and a simple edge from the cycle containing the double edge. So, m3 Å ( n3 ) / 2(( r2 ) / ( n0r 2 )) / r, which by part (iii) of Proposition 6 is also minimized by r Å n/2 . Thus, the best graph of this type, M8 , is obtained as follows: Start with a path of length two, double each edge, insert the n 0 3 nodes alternately into each double-edge, and double an edge on the resulting cycle having the most nodes. The values of m2 and m3 depend on the value of k Å n mod 2. Specifically, n 2 k Å 0: m2 Å 2 Å 2 m3 Å k Å 1: m2 Å n01 2 2 m3 Å n 2 0 2n , 4 SD n 3 / SD n 3 Fig. 9. Type4 multigraphs in V(7, 9). n /4 2 / n n3 0 n ; Å 2 6 Å n 2 0 2n / 1 , 4 2 n/1 2 2 / 2m2 / n 0 1 n3 0 n Å . 2 6 Thus, for any value of n, we obtain m2 (M8 ) ¢ (n 2 0 2n)/4 and m3 (M8 ) Å (n 3 0 n)/6. Finally, a multigraph is of Type4 if it is constructed in the following manner: STEP 1. Start with a tree on four nodes. STEP 2. Double each edge. STEP 3. Insert n 0 4 nodes randomly in the double edges, leaving at least one double edge unchanged. If the nodes were inserted in two of the double edges, the resulting multigraph is either a bicycle with a pendent double edge (M11 , M12 , or M13 ) or two cycles joined by a double bridge; else, the multigraph consists of an (n 0 2)-cycle with either two pendent double edges (M14 or M15 ) or a pendent doubled path of length two (M16 ). (See Fig. 9 for an illustration.) For ease of describing the combinatorial formulas for m2 and m3 , if the nodes are inserted in only one of the double edges formed in Step 2, then one of the other double edges is considered to be a cycle consisting of two simple edges, while the other is treated as a double edge (see M14 , M15 , M16 in Fig. 9). Let r be the number of simple edges on one cycle, and n 0 r, the number of simple edges on the other cycle. There are two ways to disconnect a Type4 multigraph by removing two edges: either remove two simple edges 8U1F / 8U1F$$0815 05-14-98 08:07:51 from the same cycle or remove the double edge. Thus, m2 Å ( r2 ) / ( n0r 2 ) / 1. By part (i) of Proposition 6, m2 is minimized when r Å n/2 . There are three ways to disconnect a Type4 multigraph by removing three edges: remove any three simple edges, remove two simple edges from the same cycle and a multiple edge, or remove the double edge and any other edge. Therefore, m3 Å ( 3n ) / 2(( r2 ) / ( n0r 2 )) / n. Again, applying Proposition 6(i), m3 is minimized when r Å n/2 . Thus, the best multigraph of Type4, M11 , is obtained when the nodes are inserted as evenly as possible into two of the double edges. It follows immediately from the discussion above that m2 (M8 ) õ m2 (M11 ), and m3 (M8 ) õ m3 (M11 ), so M8 is the best multigraph among all multigraphs of Type3 or Type4. We now compare the values of m2 and m3 for the multigraphs M1 and M8 . Since m2 (M1 ) ° (n 2 0 3n / 2)/ 6 and m2 (M8 ) ¢ (n 2 0 2n)/4, m2 (M8 ) 0 m2 (M1 ) ¢ [(n 0 2)(n / 2)]/12 ú 0 when n ú 2. Since m3 (M1 ) ° (n 3 0 n 2 0 2n / 2)/6 and m3 (M8 ) Å (n 3 0 n)/6, m3 (M8 ) 0 m3 (M1 ) ¢ [(n / 2)(n 0 1)]/6 ú 0 when n ú 1. Hence, M1 is the best multigraph from among all four types. Before we compare M1 to the UOR simple graph in V(n, n / 2), we must demonstrate that the constructions have included all possible bridgeless multigraphs in the class. To this end, we consider the graphs formed by deleting one multiple edge from a bridgeless multigraph in V(n, n / 2), that is, the graphs in V(n, n / 1) which have at most one bridge. The bridgeless multigraphs in V(n, n / 2) are obtained by adding a multiple edge anywhere if the graph in V(n, n / 1) is bridgeless; otherwise, the bridge must be doubled. We let H denote the appropriate graph in V(n, n / 1). If H is a cycle with a double edge, then the addition of another multiple edge results in either a cycle with two double edges or a cycle with a triple edge, both of Type1. If H is a cycle with a pendent double edge, then adding another multiple edge results in either a cycle with a netwa W: Networks 0815 UNIFORMLY OPTIMALLY RELIABLE GRAPHS pendent triple edge or a cycle with a double edge and a pendent double edge, both of Type3. If H is a simple bridgeless graph, then it is either a chordal n-cycle, a bicycle, or a graph which is three paths, each of length at least two, between two nodes. If H is a chordal cycle, doubling any edge yields a graph of Type1. If H is a bicycle, doubling any edge yields a graph of Type3. If H consists of three paths between a pair of nodes, doubling any edge yields a graph of Type1. If H is a graph formed by adding a pendent edge to a simple bridgeless, it must be either a chordal n-cycle with a pendent edge, a bicycle with a pendent edge, or a graph which is three paths, each of length at least two, between two nodes, with a pendent edge. Since the graph in V(n, n / 2) which results from adding the edge to H must be bridgeless, the pendent edge must be doubled, thereby resulting in a graph of Type2, Type4, or Type2, respectively. If H has a bridge between two cycles, then the only choice is to double the bridge, which gives a graph of Type4. If H is a multigraph with a pendent edge, then it is one of the following: a cycle with a double edge and a pendent edge, a cycle with a double pendent edge and a single pendent edge (emanating from either the same or different nodes), or a cycle with a pendent path of length two having one of the paths edges doubled. In all these cases, adding another multiple edge requires doubling the bridge. This yields, respectively, graphs of Type3, Type4, Type4, or Type4. Finally, it remains to compare M1 to the UOR simple graph. Since m2 (UOR) ° (n 2 0 2n / 1)/12 and m2 (M1 ) ú (n 2 0 3n)/6, m2 (M1 ) 0 m2 (UOR) ú (n 2 0 4n 0 1)/12 ú 0 for n ú 4. Since m3 (UOR) ° (5n 3 / 3n 2 0 12n / 4)/54 and m3 (M1 ) ¢ (n 3 0 n 2 0 2n)/6, m3 (M1 ) 0 m3 (UOR) ¢ (2n 3 0 6n 2 0 3n 0 2)/27 ú 0 for n ú 3. Thus, the UOR simple graph is better for n ú 4. When n Å 4, the UOR simple graph is just K4 , which has m2 Å 0 and m3 Å 4, while M1 is the multigraph obtained by starting with a triple edge, inserting a node in two of the edges, and then doubling one of the newly formed edges 8U1F / 8U1F$$0815 05-14-98 08:07:51 225 Fig. 10. The multigraph M1 for n Å 4. (see Fig. 10). For this multigraph m2 Å 1 and m3 Å 7, so the UOR simple graph is better when n Å 4, and, therefore, it is best over all graphs in V(n, n / 2). 5. CONCLUSION The work of Boesch et al. [1] gave the constructions for the UOR simple graphs in sparse classes which have n 0 1, n, n / 1, and n / 2 edges. We have shown that when the class is enlarged to include multigraphs the graphs they found are still UOR. The class V(n, n / 3) was covered by Wang [5]. Consideration of bridgeless multigraphs in this class involves many more instances. We conjecture that the UOR graphs Wang found are UOR even when the class is expanded to include multigraphs. REFERENCES [1] [ 2] [ 3] [ 4] [ 5] netwa Boesch, Li, and Suffel, On the existence of uniformly most reliable networks. Networks 21 (1991) 181–194. C. Cheng, Maximizing the total number of spanning trees in a graph: Two related problems in graph theory and optimization design theory. J. Combin. Theory 31 (1981) 240–248. F. Harary, Graph Theory. Addison-Wesley, Reading, MA (1971). F. Moskowitz, The analysis of redundancy networks. AIEE Trans. Comm. Electron. 39 (1958) 627–632. G. Wang, A proof of Boesch’s conjecture. Networks 24 (1994) 277–284. W: Networks 0815

1/--страниц