Maximizing Spanning Trees in Almost Complete Graphs Bryan Gilbert, Wendy Myrvold University of Victoria, P.O. Box 3055, MS 7209, Victoria, BC, Canada V8W 3P6 Received 26 April 1995; accepted 3 September 1996 Abstract: We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel’mans that evening out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. q 1997 John Wiley & Sons, Inc. Networks 30: 23–30, 1997 1. INTRODUCTION A graph G consists of a set V (G) of vertices and a set E(G) of edges where each edge corresponds to an unordered pair of vertices from V (G). All graphs that we consider are simple (they have no loops or multiple edges), finite, and undirected. We use n to denote the number of vertices of a graph, and m, for the number of edges. The class of (n, m)-graphs contains all simple graphs on n vertices and m edges. A spanning tree of a graph G on n vertices is an acyclic (n 0 1)-edge subgraph. Any undefined graph theoretic terms can be found in [4]. Given n vertices and m edges, how can you construct a graph having the maximum number of spanning trees? This question has applications to network reliability since under the all-terminal model, graphs with the most trees give the best topology when the edges are sufficiently unreliable (pointed out by Kel’mans in [12, p. 2119]). Correspondence to: W. Myrvold; e-mail: wendym@csr.uvic.ca Contract grant sponsor: NSERC Under this model, the vertices are assumed to be perfectly reliable and edges operate independently at random with the same probability p. The network is operational if all the vertices can communicate with each other or, equivalently, if there exists at least one operational spanning tree. A network is uniformly the best topology under this model if it is more reliable than any other (n, m)-graph regardless of the probability of edge operation. Kel’mans [17] proved that uniformly most reliable graphs do not always exist, and this was independently rediscovered in [21]. Colbourn’s monograph [8] provides a nice survey up to 1987 of the results for all-terminal reliability and other reliability problems. Boesch’s survey of 1986 [1] introduces the important principles for uniformly most reliable networks and summarizes the results up to that date. The topologies with a maximum number of trees are known for very sparse graphs (having up to n / 3 edges). It has also been proved that these graphs are uniformly most reliable by Boesch et al. [3] for up to n / 2 edges and by Wang [27] for n / 3 edges. The best graphs are summarized in the following table: q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/010023-08 23 8U11 / 8U11$$0766 06-09-97 15:09:59 netwas W: Networks 766 24 GILBERT AND MYRVOLD m õn 0 1 n01 n n/1 n/2 n/3 Graphs With the Most Trest Every graph since all have no trees Any tree An n-cycle A u-graph with path lengths as even as possible A particular subdivision of K4 (see Fig. 1) A particular subdivision of K3,3 (see Fig. 2) Ref. [28] [26] [3] In a regular complete multipartite graph, the vertices can be partitioned into sets of equal size so that within a set no two vertices are adjacent and every two vertices chosen from two different sets are adjacent. A design theory result of Cheng [6] when reformulated in graph theoretic terms [7] gives a proof that regular complete multipartite graphs maximize the number of trees over graphs on the same numbers of vertices and edges. It is not known if these graphs are uniformly most reliable. The topologies with a maximum number of trees are also known for very dense graphs (when at most n 0 2 edges are removed from the complete graph). We use Kn to denote the complete graph on n vertices. The complement GV of a graph G with respect to Kn is the n-vertex graph containing exactly the edges of Kn which are not in G. Because the graphs that we consider are close to being complete, it is often easier to consider the complements. When the number of edges is at most n/2 less than that in the complete graph Kn , the best topology is the graph whose complement consists of a set of independent Fig. 2. The best graph on n / 3 edges; subdivision of edges is done in alphabetic order (A, B, C, . . .). edges. This was proved independently by Kel’mans and Chelnokov [17] and Shier [24]. It has also been shown that these graphs are uniformly most reliable by using a reliability increasing operation called swing surgery [23]. The remaining dense cases were characterized by Petingi and co-workers [21, 22]. They also characterized the best graphs when n Å 3k edges are removed (k is an integer) or when n 0 1 edges are removed and n Å 3k / 2. In this paper, we developed a very simple algebraic proof technique for ranking graphs according to the number of trees. The technique is applicable to all graphs whose complements are a union of paths and cycles (including paths on one vertex, i.e., isolated vertices). Our theorems permit rankings of these graphs extending beyond that attained by Petingi and co-workers [21, 22]. A graph is almost-regular if the degrees of its vertices differ by at most one. This implies that the degrees are all the same if possible or there are only two consecutive values in the degree sequence. If attention is restricted to the almost-regular graphs, then we are able to characterize the graphs with the most trees in all cases where up to n edges are removed from the complete graph. It remains to be shown that almost-regularity is a necessity for the cases which were not covered by Petingi and co-workers [21, 22]. Section 2 introduces the spanning tree counting formulas that we require. These are used to justify our new algebraic technique in Section 3. This technique is applied to rank various classes of graphs according to the number of trees in Section 4. Then, these theorems are utilized to characterize the almost-regular graphs with the most trees in Section 5. Finally, we conclude in Section 6 with a list of the most promising areas for future research. The symbolic algebra package MAPLE proved invaluable for creating and checking all of our algebraic results. 2. PATH AND CYCLE FORMULAS Fig. 1. The best graph on n / 2 edges; subdivision of edges is done in alphabetic order (A, B, C, . . .). 8U11 / 8U11$$0766 06-09-97 15:09:59 The most common formula used for finding the number of trees in a graph is the Kirchhoff matrix tree theorem netwas W: Networks 766 MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS 25 Fig. 3. The complement spanning tree matrix and the complement graph. [18]. A proof which provides graph theoretic intuition can be found in Gibbon’s book [10, pp. 49–54]. In this section, we introduce a formula that is algebraically equivalent, but more convenient for the graphs that we consider since the formulation is in terms of the complement of the graph. Temperley was the first to use this [25]. The complement spanning tree matrix, KV (G), of a graph G with respect to Kn has ith diagonal entry equal to n minus the degree of the ith vertex of GV , and offdiagonal entry (i, j) is 1 if ( £i , £j ) is an edge of GV and 0 otherwise. Proofs of this next theorem occur in several references including [5, p. 39, Theorem 2.5.4]. Theorem 2.1. The number of spanning trees of G, t(G), is equal to 1 ∗ det(KU (G)). n2 j As an example to illustrate the concepts just introduced, consider the graph whose complement consists of two independent edges plus some isolated vertices. The complement graph and its complement spanning tree matrix are pictured in Figure 3. The determinant of KV (G) is n n (1 0 2/n) 2 and, hence, the number of trees equals n n0 2 (1 0 2/n) 2 . Moon introduced the generic form f (n, G) of a graph G [20]. It is equal to (1/n n ) ∗ det(KV (GV )). For example, f (n, G), where G is the graph in Figure 3, is equal to (1 0 2/n) 2 . This leads to the following nice corollary which shows that to compute the number of trees of a graph we can consider the components of the complement independently. This corollary has been stated by numerous authors in various guises. algebra which states that the determinant of a block diagonal matrix is the product of the determinants of the blocks. If the vertices of the components of GV are given consecutive vertex labels, then in KV (G), each results in a block. If you divide each row of the complement spanning tree matrix by n, then the resulting determinant is the product of the generic forms of the components. Thus, our corollary is obtained from Theorem 2.1 since dividing each row of a matrix by n and premultiplying by n n preserves the value of the determinant. j We now give the generic forms for a path on k vertices (Pk ) and a cycle on k vertices (Ck ) with respect to Kn . These results are implicit in the work of Kel’mans [12, 13] and can also be found in the technical report of Boesch and Suffel [2]. Proofs are also given in detail in Gilbert’s thesis [11, Chap. 4]. To derive these formulas, the complement spanning tree matrix is used to define a recurrence which is solved using standard methods. Theorem 2.3. The generic form f (n, Pk ) for Pk 1 ° k ° n, and n ú 4 is given by q 1 0 2 / n 2 0 4n ) k ((n n 2 0 4n q 2 kn k0 1 q 0 (n 0 2 0 n 2 0 4n ) k ). The restriction n ú 4 is not a serious limitation since it is easy to classify all graphs on four or fewer vertices with respect to the number of trees that they have. Theorem 2.4. The generic form f (n, Ck ) for Ck , 3 ° k ° n, and n ¢ 4, is given by q 1 ((n 0 2 / n 2 0 4n ) k 2 kn k q / (n 0 2 0 n 2 0 4n ) k / ( 02) k/ 1 ). Corollary 2.2. If the complement of the n-vertex graph G has k components G1 , G2 , . . . , Gk (or, equivalently, GV Å G1 / G2 , rrr / Gk ), then t(G) Å n n02 ∏ kiÅ1 f (n, Gi ). Proof. First recall the elementary result from linear 8U11 / 8U11$$0766 06-09-97 15:09:59 j j 3. OUR NEW ALGEBRA In this section, we explain how to simplify the formulas from the previous section. This culminates in a proof netwas W: Networks 766 26 GILBERT AND MYRVOLD technique that permits short proofs of many interesting results (given in the next section). For notational convenience, we define the following functions of n: x k f (n, Pk ) Å 1 (x 2 k 0 1) n k0 1s and r å r(n) Å n 0 2 q x k f (n, Ck ) Å s å s(n) Å n 2 0 4n 1 1 (x 2 k / 1 / 2dk x k ) Å k (x k / dk ) 2 . k n n p å p(n) Å r / s q å q(n) Å r 0 s x å x(n) Å p/2. We start with a trivial observation about the function x which is required for all the proofs in the next section. Lemma 3.1. For n ¢ 5, x ú 2. 4. COMPARATIVE RESULTS Proof. Clearly, x is an increasing function of n. Also, x(5) ú 2. j For our algebraic proof technique, we define a function A(G) equal to (x 2 k 0 1) for the path Pk , and (x k / dk ) 2 for the cycle Ck , where dk is 1 if k is odd and 01 if k is even. We see in the proof of the next theorem a rationale for defining this function. Theorem 3.2. If G and H are both graphs whose complements are unions of paths and cycles on n vertices and m edges, n ¢ 5, then t(G) ú t(H) if and only if ∏ ∏ A(C) ú C is a component of GU A(C). C is a component of HU Proof. We start with the generic forms for paths (Theorem 2.3) and cycles (Theorem 2.4) given in the previous section. Rewriting using our notation given above and rearranging so the 2 k is divided into each term rather than being factored out in front gives f (n, Pk ) Å 1 n k0 1s SS D S D D p 2 It is easy to show that the number l of paths (including P1’s) of G or H is a constant dependent on m. Also, since multiplying both spanning tree formulas further by n ms l preserves the relative ranking, we see that this theorem is true. j k q 2 0 k We begin this section with the definition of a partial order ¥ over (n, m)-graphs established by Kel’mans [14, p. 254]. If we consider two graphs G and H with k vertices, then we define G ¥ H if t(Kn 0 G) ú t(Kn 0 H) for all n ¢ k. We point out that ¥ is not a total order. Kel’mans and Chelnokov gave a complicated example of a pair of ¥-incomparable graphs in [17, p. 211]. Later in a 1980 research announcement, Kel’mans [15] stated, without details, a number of other examples of ¥-incomparable graphs. One simple example is as follows: ¥ cannot be used to order the two 8-vertex graphs G Å P3 / P3 / P1 / P1 and H Å P4 / K1,3 because t(K8 0 G) Å 40,000 ú t(K8 0 H) Å 39,984 but t(K9 0 G) Å 944,784 õ t(K9 0 H) Å 947,520. Other examples of graphs incomparable with respect to ¥ include nonisomorphic graphs with the same number of trees ( cospectral graphs, see [9, Chap. 6 ] ) . In this section, we rank some families of graphs according to this operator. First, we consider graphs whose complements are paths (Section 4.1). The next step is to consider cycles (Section 4.2). Our final theorems involve graphs whose complements are a mixture of paths and cycles (Section 4.3). and 1 f (n, Ck ) Å k n SS D S D p 2 k / q 2 k 4.1. RANKING PATH COMPONENTS D / 2dk . Multiplying the formulas for t(G) and t(H) given by Corollary 2.2 by x n preserves the rankings of the two formulas. Applying x k to each term corresponding to a Pk or a Ck and observing that pq Å 4, we get 8U11 / 8U11$$0766 06-09-97 15:09:59 In this section, we prove that evening out the lengths of paths increases the number of spanning trees. This result is originally due to Kel’mans [14, Lemma 6.8, p. 258] (note that this paper uses the notation Cn to represent a path on n vertices). Theorem 4.1. Let m ¢ 4 (and n ¢ 5), and let netwas W: Networks 766 MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS 27 which the lengths have the same parity. The second theorem handles the case in which the parities differ. G(c) Å P m / 2 /c / P m / 2 0c , where 0 ° c õ m/2 . Then, Theorem 4.3. Let m ¢ 6 and 3 ° k õ m 0 k 02. Then, G(c) ¥ G(c / 1). Proof. Let m ¢ 5. For a fixed c, let k Å m/2 / c. From Theorem 3.2, it suffices to show that if k is odd Ck / Cm0k ≥ Ck/2 / Cm0k02 if k is even. and A(Pk )A(Pm0k ) ú A(Pk/1 )A(Pm0k01 ), or, equivalently, that Ck / Cm0k ¥ Ck/2 / Cm0k02 j Theorem 4.4. Let m ¢ 6 and 3 ° k õ m 0 k 0 1. Then, (x 2 k 0 1)(x 2 ( m0k ) 0 1) ú (x 2 ( k/ 1 ) 0 1)(x 2 ( m0k0 1 ) 0 1). We multiply this out and simplify algebraically to get the inequality 4.2. RANKING CYCLE COMPONENTS We now proceed to consider collections of cycles in the complement graph. The next theorem is new and allows us to extend the work done by Kel’mans [14], Kel’mans and Chelnokov [17], and Petingi [21]. Petingi has a version of the following where k is fixed at three. Theorem 4.2. Let m ¢ 6 and 3 ° k ° m 0 k. Then, Ck / Cm0k ¥ Cm Ck / Cm0k ≥ Ck/1 / Cm0k01 if k is even. j The proofs of these results are a straightforward application of our algebraic technique, so we omit them. Complete details can be found in [10]. 4.3. Ranking Mixed Path and Cycle Components We first show that replacing a cycle and an isolated vertex with a path increases the number of spanning trees. Kel’mans [14, Lemma 6.9, p. 258] also proved this using a different proof technique. Theorem 4.5. For k ¢ 3 (and n ¢ 5), Pk/1 ¥ Ck / P1 . Proof. By Theorem 3.2, we need to prove that if k is odd (x 2 ( k/ 1 ) 0 1) 0 (x k / dk ) 2 (x 2 0 1) ú 0. and Ck / Cm0k ≥ Cm We actually prove something stronger, namely, that (replacing dk by 1) if k is even. Proof. We apply Theorem 3.2 and note that it suffices to compare the square roots of each term (this works when all components are cycles). Multiplying out and canceling terms results in the equation dm0k x k / dk x m0k / dkdm0k 0 dm ú 0. / 8U11$$0766 06-09-97 15:09:59 (x 2 ( k/ 1 ) 0 1) 0 (x k / 1) 2 (x 2 0 1) ú 0. This implies that x 2 k 0 2x k/ 2 / 2x k 0 x 2 ú 0. (1) A simple truth table can be used to show that dkdm0k Å 0 dm . Thus, it is obvious (since x ú 2 by Lemma 3.1, and by definition, k ° m 0 k) that Eq. (1) has the same sign as dk , thus proving our theorem. j The above theorem compares one large cycle with two smaller ones. The next two theorems compare pairs of cycles. The first theorem compares two pairs of cycles in 8U11 if k is odd and (x 2 0 1)(x 2 k 0 x 2 ( m0k0 1 ) ) ú 0. But this is obviously true because x ú 2 (Lemma 3.1), and by definition, k ú m 0 k 0 1. j Ck / Cm0k ¥ Ck/1 / Cm0k01 But this is true because k ¢ 3 and x ú 2 (Lemma 3.1). j We now show that C3 / Pk03 ¥ Pk , for k ¢ 5. Kel’mans stated this result without proof in [14, p. 260]. Theorem 4.6. Let k ¢ 4 (and n ¢ 5). Then, netwas W: Networks 766 28 GILBERT AND MYRVOLD Lemma 4.8. (a) C3 / P3 / P2 ¥ P4 / P4 (b) C3 / 3r P2 ¥ 3r P3 (c) C3 / 2r P2 ¥ P4 / P3 . C3 / Pk03 ¥ Pk . Proof. By Theorem 3.2, we need to show that A(C3 )A(Pk03 ) 0 A(Pk ) ú 0, Petingi’s Lemma 5.10 parts (a), (d), and (e) [21, p. 38] are equivalent to our Lemma 4.8 parts (a), (b), and (c), respectively. or, equivalently, that (x3 / 1) 2 (x 2 ( k0 3 ) 0 1) 0 (x 2 k 0 1) ú 0. Simplify algebraically to get 5. MAXIMIZING SPANNING TREES (2x 2 k0 3 0 x 6 ) / (x 2 k0 6 0 2x 3 ) ú 0. Each parenthesized term (and, hence, the whole expression) is clearly positive since x ú 2 (Lemma 3.1) and k ¢ 5. j Next, we show that a 3-cycle and a path is better than a larger cycle and shorter path. Kel’mans states that this can be proved [15, Note, p. 260] and Petingi also mentions it [21, Fact 3.8, p. 33] referring to Kel’mans for the proof. Theorem 4.7. Let k 0 c ú 0, and let c ú 0. Then, C3 / Pk ¥ C3/c / Pk0c . Proof. By Theorem 3.2, we need to show that A(C3 )A(Pk ) 0 A(C3/c )A(Pk0c ) ú 0. We actually show something stronger, namely, that (replacing dk by 1) A(C3 )A(Pk ) 0 (x c/ 3 / 1) 2 A(Pk0c ) ú 0. We do this by demonstrating that the maximum value of (x c/ 3 / 1) 2 A(Pk0c ) given that c ¢ 0 is attained when c Å 0 (corresponding to C3 and Pk ). If we multiply out the expression (x c/ 3 / 1) 2 A(Pk0c ) and ignore the terms that are independent of c, we get 2x 2 k0c/ 3 / x 2 k0 2 c 0 x 2 c/ 6 0 2x c/ 3 . The first two positive terms are clearly maximized when c Å 0. Also, the last two terms make the smallest negative contribution when c Å 0. j The special cases in this next lemma are needed to characterize the graphs with the most trees. The proofs are straightforward applications of our algebra and so we omit them. 8U11 / 8U11$$0766 j 06-09-97 15:09:59 All along, we have been considering graphs whose complements are a union of paths and cycles (including isolated vertices which are P1 ). In this section, we characterize the graphs in this family with the most trees. It is useful to first consider how the cycles should be configured in a graph with the most trees. Lemma 5.1. The 2-regular (n, m)-graph (n ¢ 5) whose complement contains a maximum number of trees consists of C3’s and at most one of a C4 or a C5 . Proof. In the graph with the most trees, there are no spanning tree increasing operations that can be applied. We use this fact to isolate the structure of the graphs with the most trees. First, the best graph has no Ck’s for k ¢ 6 because by Theorem 4.2 replacing Ck , k ¢ 6, by C3 and Ck03 increases the number of trees. Consequently, all cycles in the best graphs have length at most five. If there is a C4 and a C5 , replacing these by C3 and C6 increases the number of trees (Theorem 4.4). Therefore, there can be C4’s or C5’s but not both. If there are two C4’s, replacing them by C3 and C5 increases the number of trees again by Theorem 4.4. Similarly, if there are two C5’s, replacing them by C3 and C7 increases the number of trees (Theorem 4.3). Thus, we have shown that the best graph has all C3’s except for possibly either one C4 or one C5 as required. j We are now ready to characterize the almost-regular graphs with a maximum number of trees. The proof is original, but the only new conclusions are the situations with n or n 0 1 edges removed from the complete graph not covered by [4] (described in the introduction). Theorem 5.2. Of the family of (n, m)-graphs consisting of a union of paths and cycles, the ones for which the complements have a maximum number of trees are the almost-regular graphs equal to 1. For m õ n/2, P2’s and P1’s. netwas W: Networks 766 MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS 2. For n/2 ° m ° n 02, C3’s, and P2’s and either P2 or P3 or two P3’s. 3. For m Å n 0 1, C3’s, and P2’s and either P2 or P3 or P4 . 4. For m Å n, at most one of C4 or C5 plus C3’s. REFERENCES [1] [2] Proof. First, the degree sequence is almost regular because of Theorem 4.5, or, equivalently, if there are isolated vertices, then there are no cycles. Next, the paths are as even in length as possible by Theorem 4.1. Furthermore, the paths contain at most two degree two vertices in total since Theorem 4.6 and Lemma 4.8 combined indicate that if there are more than two degree two vertices in paths the number of trees is increased by shortening the paths and adding a C3 . By Lemma 5.1, the collection of cycles in the best graph is all 3-cycles except possibly for one C4 or one C5 . By Theorem 4.7, it is better to have a C3 with a longer path than a C4 or a C5 with a shorter path. j [3] [4] [5] [6] [7] [8] 6. FUTURE WORK [9] It still remains to indicate which of the graphs that we have considered are uniformly most reliable. Some obviously are not (e.g., see [16]). The most promising avenue of approach is a technique such as the swing surgery [23], although may be a ‘‘reliability algebra’’ similar to our ‘‘spanning tree algebra’’ could be developed to distinguish between the ones with the same degree sequence. The next open dense case for characterizing the graphs with the most trees is when n / 1 to 3n/2 edges are removed from the complete graph. The first step here would be to conjecture a pattern for the best graphs. We found it very helpful to use a program which computed generic forms when developing the pattern for the range that we considered and recommend this as a first step. To date, except for the trivial cases on n 0 1 or fewer edges, all known (n, m)-graphs with a maximum number of trees are almost-regular. Furthermore, it seems intuitive that graphs with a maximum number of trees have no multiple edges [until you are forced to have them because the number of edges exceeds n(n 0 1)/2]. Either eigenvalue techniques (see, e.g., [16]) or spanning tree increasing operations may prove useful in proving that these things are necessary. For the sparse cases, we observe that in the known cases the underlying 3-regular substructure is the optimal 3-regular graph. We conjecture that this is always true and that edges are subdivided as evenly as possible, but not necessarily in some order such as in Figures 1 and 2. 8U11 / 8U11$$0766 06-09-97 15:09:59 29 [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] netwas F. T. Boesch, On unreliability polynomials and graph connectivity in reliable network synthesis. J. Graph Theory 10(3) (1986) 339–352. F. T. Boesch and C. L. Suffel, A survey of the algebraic approach to the study of spanning trees. Unpublished report (1984). F. T. Boesch, X. Li, and C. Suffel, On the existence of uniformly optimally reliable networks. Networks 21 (1991) 181–194. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, New York (1980). R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory. Cambridge University Press, New York (1991). C.-S. Cheng, Optimality of certain asymmetrical experimental designs. Ann. Stat. 6 (1978) 1239–1261. C.-S. Cheng, Maximizing the total number of spanning trees in a graph; two related problems in graph theory and optimum design theory. J. Combin. Theory, Ser. B 31 (1981) 240–248. C. J. Colbourn, The Combinatorics of Network Reliability. Oxford University Press, New York (1987). D. M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs. Academic Press, New York (1980). A. Gibbons, Algorithmic Graph Theory. Cambridge University Press, Cambridge (1989). B. Gilbert, Maximizing spanning trees in almost complete graphs. Master’s Thesis, Department of Computer Science, University of Victoria, Victoria, BC (1995). A. K. Kel’mans, The number of trees in a graph, I. Automation and Remote Control—Translated from: Avtomatika i Telemekhanika (Russian) 26(12) (1965) 2194–2204. A. K. Kel’mans, The number of trees in a graph, II. Automation and Remote Control—Translated from: Avtomatika i Telemekhanika (Russian) 27(2) (1966) 56– 65. A. K. Kel’mans, Comparison of graphs by their number of spanning trees. Discr. Math. 16(3) (1976) 241–261. A. K. Kel’mans, Graphs with an extremal number of spanning trees: A research announcement. J. Graph Theory 4 (1980) 119–122. A. K. Kel’mans, On graphs with randomly deleted edges. Acta Math. Acad. Sci. Hung. 37(1–3) (1981) 77–88. A. K. Kel’mans and V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees. J. Combin. Theory, Ser. B 16 (1974) 197–214. G. Kirchhoff, Über die Ausflösung der Gleichungen auf welche man bei der Untersuchungen der Linearen Verteilung Galvanisher Ströme geführt wird. Poggendorf Ann. Phys. 72 (1847) 497–508. J. W. Moon, Enumerating labelled trees. Graph Theory and Theoretical Physics, (F. Harary, Ed.). Academic Press, New York (1967) 261–272. W: Networks 766 30 GILBERT AND MYRVOLD [20] W. Myrvold, K. H. Cheung, L. B. Page, and J. E. Perry, Uniformly-most reliable networks do not always exist. Networks 21 (1991) 417–419. L. Petingi, On the characterization of graphs with maximum number of spanning trees. PhD Thesis, Stevens Institute of Technology, Hoboken, NJ (1991). L. Petingi, F. Boesch, and C. Suffel, On the characterization of graphs with maximum number of spanning trees. Accepted to Discrete Mathematics, 1997. A. Satyanarayana, L. Schoppmann, and C. L. Suffel, A reliability-improving graph transformation with applications to network reliability. Networks 22 (1992) 209– 216. D. R. Shier, Maximizing the number of spanning trees [21] [22] [23] [24] 8U11 / 8U11$$0766 06-09-97 15:09:59 [25] [26] [27] [28] netwas in a graph with n nodes and m edges. J. Res. Nat. Bur. Stand., Sect. B 78 (1974) 193–196. H. N. V. Temperley, On the mutual cancellation of cluster integrals in Mayer’s fugacity series. Proceed. Phys. Soc. 83 (1964) 3–16. S. S. Tseng and L. R. Wang, Maximizing the number of spanning trees of networks based on cycle basis representation. Int. J. Comput. Math. 28 (1989) 47–56. G. Wang, A proof of Boesch’s conjecture. Networks 24 (1994) 277–284. J. F. Wang and M. H. Wu, Network reliability analysis: On maximizing the number of spanning trees. Proceed. Nat. Sci. Coun. Repub. China, Part A, Phys. Sci. Eng. 11(3) (1987) 193–196. W: Networks 766

1/--страниц