Microsoft Word - MATH090915-f -edited_corrected.doc 81-86 SQU Journal For Science, 15 (2010) © 2010 Sultan Qaboos University 81 Formulas for the Number of Spanning Trees in a Chain of Cycles Thomas Bier Department of Mathematics and Statistics, College of Science, Sultan Qaboos University, P.O. Box 36, Postal code 123, Muscat, Sultanate of Oman, Email: tbier@squ.edu.om. لعدد األشجار المولدة في سالسل الدوراتصيغة بييروماسث ، اوجدنا صيغة لعدد اشجار المولدات في سلسلة الدورات و التي لها على االقل حافة واحدة مترابطة مشتركة :خالصة .هذه الصيغة تستعمل الخواص االولية للكسور الغير منتهية. و لكن بحجم دورات مختلف ABSTRACT: We give a formula for the number of spanning trees in a chain of cycles that have connected intersection of one edge but where the cycles have variable sizes. The formula uses basic properties of continued fractions. KEYWORDS: Spanning trees, Arboricity and Continued fractions. 1. Sequences of Cycles onsider a graph which is a sequence of n cycles 123..nC where cycles (of variable size but larger than two) with adjacent labels share a single common edge. An example with 5n = is given in Figure 1. Figure 1. Some sequences of cycles. C THOMAS BIER 82 We should like to derive a formula for the tree complexity, i.e. the number of spanning trees, for such graphs that uses a continued fraction expansion rather than the matrix tree formula. If we glue two cycles of lengths 1g and 2g sharing one common edge, then the situation is easy, and there are precisely 1 2 1g g − spanning trees. Indeed there are ( )( )1 21 1g g− − spanning trees containing the common edge and there are 1 2 2g g+ − spanning trees that do not contain the common edge. For example in the left of the above Figure we will find 34 spanning trees. We may express this in the following arithmetic way. The fraction 1 2 1 2 2 11 g g g g g − − = has a numerator which is the number of spanning trees of the union of two cycles, and it has a denominator which is the number of spanning trees of a single cycle of length 2g . Let us now consider a larger case as in the right hand side of the Figure. Let us assume that there are 5 cycles and they have sizes 1 2 3 4 5, , , , 2g g g g g > . Thus for the example in the right hand side of Figure we have 1 4g = , 2 6g = , 3 5g = , 4 4g = , and 5 7g = . We may then find the number of spanning trees of such a graph by first computing the numerator of the expression 1 2 3 4 5 1 1 1 1 x x x x x + + + + This turns out to be 3 4 5 3 5 1 1 1 4 5 2 3 4 5 2 3 2 5 4 5 2 2 5 3 4 5 3 5 3 4 5 1 1 1 1 1 1 x x x x x x x x x x x x x x x x x x x xx x x x x x x xx x x + + + = + = + + + + + ++ + + ++ + Thus the numerator of the expression is just 1 2 3 4 5 1 2 3 1 2 5 1 4 5 3 4 5 1 3 5x x x x x x x x x x x x x x x x x x x x+ + + + + + + Now to get the number of spanning trees we substitute ( )1 .kk kx g= − and take the absolute value. This yields the expression 1 2 3 4 5 1 2 3 1 2 5 1 4 5 3 4 5 1 3 5| |g g g g g g g g g g g g g g g g g g g g− + + + + − − − which is just the number of spanning trees of the graph under discussion. In our example in the right hand side of the Figure we get for the number of spanning trees the positive integer 4 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 7 - 4 ⋅ 6 ⋅ 5 - 4 ⋅ 6 ⋅ 7 - 4 ⋅ 4 ⋅ 7 - 5 ⋅ 4 ⋅ 7 + 4 + 5 + 7 = 2836. Let us state the result in the general case. FORMULAS FOR THE NUMBER OF SPANNING TREES 83 Theorem: If we simplify the finite continued fraction in the n variables 1 2 3, , ,...., nx x x x as a simple quotient 1 2 3 1 2 3 2 3 1 [ , , , , ]1 1 [ , , , ] 1 1 n n n n x x x x x x x xx x x x− + = + + + … and if we substitute ( )1 .ii ix g= − then the absolute value of the numerator on the RHS of the above equation is the number of spanning trees in the chain of cycles 12...nC . For the proof of this formula we first remark that for the bracket [ ]1 2 3, , ,...., nx x x x defined by 1 2 3 1 2 3 2 3 1 [ , , , , ]1 1 [ , , , ] 1 1 n n n n x x x x x x x xx x x x− + = + + + … We have the well known relation (Bier 1995) 1 2 3 1 2 3 3[ , , , , ] [ , , , ] [ , , ]n n nx x x x x x x x x x= ⋅ +… … … Considering the substitution ( )1 .ii ix g= − this easily implies [ ] [ ]1 2 3, 3 1 2 3, , ..., ,..., . , ,...,n n ng g g g g g g g g g⎡ ⎤ + =⎣ ⎦ (1) Now we can do a proof by induction on n. It is clear that for 1n = the result for both the formula and for the counting is g1, so we may start the induction. Then for the induction step the right hand side of equation (1) is 1g times the number of spanning trees for the union of cycles 23...nC . We write this as a sum of four terms. 1 2 3 1 12 12 1 12 12[ , , , ] ( 1) ( ) ( ) ( 1) ( ) ( )ng g g g g M e M e g N e N e⋅ = − ⋅ + + − ⋅ +… (2) To explain this let 12 1 23...ne C C= ∩ be the common edge of the first and the second cycle. Let ( )12M e be the number of spanning trees of 23...nC which contain e12 and let ( )12N e be the number of spanning trees of 23...nC which do not contain 12e . Then (1) follows from the fact that [ ]2 3, ,..., ng g g is the number of spanning trees of 23...nC , and each such spanning tree either contains or does not contain 12e so that [ ] ( ) ( )2 3 12 12, ,..., ng g g M e N e= + . Then multiply this equation by 1g and rearrange to get (1). We can THOMAS BIER 84 now see by inspection that ( ) ( )1 121g M e− ⋅ is the number of spanning trees of 23...nC which contain 12e . Indeed each spanning tree that contains 12e must miss precisely one other edge of 1C , and there are 1 1g − choices for these missing edges. We may now use the following obvious fact: Assume that ,G H are two simple (connected) graphs and that G H∨ is the graph that is obtained by glueing these two graphs together at a single vertex. Then the number ( )k G H∨ of spanning trees of this one point union G H∨ is the product of the number of spanning trees of the two parts: ( ) ( ) ( )k G H k G k H∨ = ⋅ . Recall that for the complete graph we have Cayley's formula ( ) 2nnk K n −= . For the n -cycle nCy obviously we have ( )nk Cy n= . As a simple application of the above fact we have ( ) .nn n nK Cy Cy nκ ∨ ∨ = We can see by inspection, using the lemma twice and the induction hypothesis that the last term in (2) which is ( )12N e is just equal to [ ]3 4, ,..., ng g g . Indeed ( )12N e is the number of spanning trees of { }23.. 12\nC e . Let 1 2,T T be the two tail ends that remain from 2C after removing 12e . By using the above fact twice with 34.. 1 2,nG C T H T= ∨ = and with 34.. 1,nG C H T= = we get the equations: 23... 12 34... 1 2 34... 1 2 34... 1 2( \ { }) ( ) ( ) ( ) ( ) ( ) ( ) | | ,n n n n nC e C T T C T T C g g gκ κ κ κ κ κ κ= ∨ ⋅ = ⋅ ⋅ = = … where the second last step comes from ( ) 1k T = for any tree T , and the last step is the inductive assumption. Finally we claim that the sum of the two central terms of (2) ( ) ( ) ( )12 1 121 .M e g N e+ − is the number of all spanning trees of 12...nC that do not contain 12e . To see this, distinguish the two cases when the spanning tree does or does not contain all the remaining edges of { }1 12\C e . The number of spanning trees of 12..nC that do contain all the edges of 1 12\C e are in bijective correspondence with the spanning trees of 23..nC and hence their number is ( )12M e . The trees that miss another edge of 1C are in bijective correspondence with the ordered pairs ( ),e T where e is the other missing edge, and where T is a spanning tree of 23..nC that does not contain the edge 12e . Thus their total number is ( ) ( )1 121 .g N e− . Both terms in ( ) ( ) ( )12 1 121 .M e g N e+ − have been accounted for. This proves the induction step by a counting argument, and hence (1) is true. Note that the use of the matrix tree theorem may not be practical in this general case. 2. Special Cases and Discussion Let us consider the special case in which all cycles have the same length, say g. Then from (1) we get for the number nk of such a union of n cycles the recursion relation 1 2n n nk g k k− −= ⋅ − FORMULAS FOR THE NUMBER OF SPANNING TREES 85 Obviously we have the boundary conditions 0 11,k k g= = .We may the solve the recursion in the standard way by first finding the characteristic roots of the equation 2 1gλ λ∧ = ⋅ − which are 2 1,2 4 2 g g λ ± − = The general solution for 0k then has the form 2 24 4 ( ) ( ) 2 2 n n n g g g g a bκ + − − − = ⋅ + ⋅ and from the boundary conditions we get 2 2 2 2 4 2 4 2 ( ) and ( ) . 2 4 2 4 g g g g a b g g − + − − = = − − This then gives the general solution 2 2 1 1 2 4 41 [( ) ( ) ] . 2 24 n n n g g g g g κ + + + − − − = ⋅ − − For the cases 3g = in (Bogdanowicz 1994) etc. and 4g = in (Sedlacek 1970) etc., this solution already appeared in the literature for certain specific graphs, namely the fan and the ladder graphs. But from the approach given here it appears that for all graphs of the form 12..nC the results of these computations are the same, while most authors on the subject seem to restrict themselves to one particular family of graphs. Figure 2. Fan and related graph. For example (Bogdanowicz 1994) gives results for the fan graph on the left of the Figure 2, while the formulae are also correct for a graph as on the right side of that Figure. Similarly, various authors treat cases like the ladder on the left of the Figure 3, but one rarely sees a graph like the one on the right side which again has the same number of spanning trees. Perhaps the general theory of complexity (Ihara 1966, Hashimoto 1989, Stark et al. 1995, Northshield 1994) may help to explain such equalities. THOMAS BIER 86 Figure 3. Two different graphs with the same number of spanning trees. Similarly, various authors treat cases like the ladder on the left of the Figure 3, but one rarely sees a graph like the one on the right side which again has the same number of spanning trees. Perhaps the general theory of complexity (Ihara 1966, Hashimoto 1989, Stark et al. 1995, Northshield 1994) may help to explain such equalities. 3. References BIER, T. 1995. Eine Charakterisierung zyklischer Polytope durch Kettenbrüche, Archiv der Mathematik 16: 545-554. BOGDANOWICZ, Z.R. 2008. Formulas for the number of spanning trees in a fan, Applied Mathematical Sciences 2: 781-786, Hikari Ltd. HASHIMOTO, K. 1989. Zeta Functions of finite graphs and representations of p-adic groups, Advanced Study in Pure Mathematics, vol 15, Academic Press NY pp. 211-280. IHARA, Y. 1966. On discrete Subgroups of the two by two projective linear group over p-adic fields, J. Math Soc Japan 18: 219-235. NORTHSHIELD, S. 1994. Several Proofs of Ihara's theorem, IMA preprint series No 1459. SEDLACEK, J. 1970. Lucas Numbers in Graph Theory, In Mathematics (Geometry and Graph Theory) Univ. Karlova, Prague p. 111-115. STARK, H. and TERRAS, A. 1995. Zeta functions of finite Graphs and Coverings, MSRI Preprint No 074-95. Received 15 September 2009 Accepted 21 February 2010