in}? .... E: .. .v ......r ......xtl: ‘37.} I! n 1.3:. Q 3.1... I. 3:31. 2.13:... g... ‘ . ... shhuhcan. v.5 l. ... . .‘1‘54‘ .7 .5 E , , 8:13.... (:1: 33.46.: ”l 5...... 3.10.4411?! :1... ., if... 1-? .7, 9 3' {or}?! If! . v 23.... r . ititq. Si... z , ....zéh... w...“ 2; pig.» . .4 Wmfiuk . .13.». E .q. a“... o. X . ‘ twig-2..- . 5.. r}. 5.. 1.. M . ‘ uwmflmn: ARM. . 65.35%.” ”5%,”: W03; .\ If VL‘Bu‘ifiwur ‘ 3. 9......» .. we... .m .~3. 4 . . 5‘ . .H . V . . 2.25 \arg. . 9H .... 5‘35! ...... 1.1.... In}. .... .52}: ... ..., O .... ‘QI-K‘gllh‘r . .24.“. tau quit-“3:30 xt‘...«...... . i iatrifiu . . .1 ...... L351: ~ . x» ) P ...v. . ... A v . . .rII. . ..3. v.9}..."ui. .2 . ‘ . 4...... kills? 23$“ :35: ’51:... 1 23.5.. \I k. :50 69.3...58. . z . In... ‘93:... .1. .- i: v I: .i.l.l:.(,. . 1.5.3.: 1.1).... tail“! Lint}! n trial-[5.»Osnv-D. Joly... n: Quilxto 1145815 300! LIBRARY Michigan State University w This is to certify that the dissertation entitled Enumeration of General Cubic Graphs presented by Gab-Byung Chae has been accepted towards fulfillment of the requirements for Ph . D . degree in Mathematics V Major professor Date _Ang.us_t_25_._2_O_Q9_ MS U i: an Affirmative Action/Equal Opportunity Institution 042771 PLACE IN RETURN Box to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 6/01 acme/ompes-ms . . :l-[IIVlIIl‘blID‘l-n. D'OO .It .0 ll Ci . ain't. ..ls. l r 4.. ..b,v..‘i|t.tfo i‘ ., ii I} f l r .lvl.’l’l .-l ..:I (I. ,l ..b..’|||\{l|\lllnll{iv \' i l Enumeration of General Cubic Graphs By Gab-Byung Chae A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 2000 ABSTRACT Enumeration of General Cubic Graphs By Gab-Byung Chae A labeled general cubic graph is a labeled cubic graph which has single edges, loops, and double edges. A claw-free cubic graph is a cubic graph which contains no induced subgraph isomorphic to K13- We first derive recurrence relations from partial differential equations whose formal power series solutions are the exponential generating functions for labeled, general cubic graphs with given connectedness. The relations are used to compute number of these graphs with a specified number of loops and multiple edges. Next, we use exponential generating functions to count claw—free cubic graphs with given connectivity. Finally, we find the asymptotic number of general cubic graphs by using inclusion and exclusion for two types of properties. To my family iii ACKNOWLEDGMENTS I would like to thank my advisor, Professor Edgar M. Palmer, for his patience, encouragement, and excellent advice. I also would like to thank Professor Bruce E. Sagan for his lectures which introduced me to combinatorics and especially graph the- ory. It is a great pleasure to thank Professor Abdol-Hossein Esfahanian , Jonathan I. Hall, and Susan E. Schuur for serving in my committee and offering helpful sug- gestion. I would like to give special thanks to Robert W. Robinson for his through reading of thesis and his many comments. Finally, I would like to thank my parents, Chae, Soo-Myun and Cho, Ok—Wha and my wife Chung, Kyung—Ah and my children, Heeyoong and Honbit, for their encouragement and support of my education. iv TABLE OF CONTENTS LIST OF FIGURES vi LIST OF TABLES vii 1 Introduction 1 2 Computing the number of Labeled General Cubic Graphs 5 2.1 Computation ................................. 5 2.2 2-connected general cubic graphs ...................... 15 2.3 Conclusion ................................... 24 3 Computing the number of Claw-free Cubic Graphs with given Con- nectivity 28 3.1 Connected claw-free cubic graphs ...................... 29 3.2 2-connected Claw-free cubic graphs ..................... 32 3.3 3—connected Claw-free cubic graphs ..................... 36 3.4 Conclusion ................................... 38 4 Asymptotic number of General Cubic Graphs 40 4.1 Inclusion and Exclusion for two types of properties ................................ 41 4.2 Configurations ................................ 44 4.3 Asymptotic number of general cubic graphs ................ 48 BIBLIOGRAPHY 58 LIST OF FIGURES 2.1 ......................................... 16 2.2 ......................................... 18 2.3 ......................................... 19 2.4 ......................................... 20 2.5 ......................................... 21 2.6 ......................................... 22 2.7 ......................................... 25 2.8 ......................................... 26 vi 2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4 3.5 LIST OF TABLES Number of general cubic graphs with 2n 5 10 ................ 9 Examples for the unimodality with 2n = 10 and s = 5 or s = 6. ..... 11 Number of 1-connected general cubic graphs with 212 S 10 ......... 12 Number of 2-connected general cubic graphs with 2n 3 12 ......... 25 Boundary conditions .............................. 30 Number of l-connected cfc graphs with 2n 3 6O ............... 33 Number of 2-connected cfc graphs with 2n 5 36 ............... 37 Number of 3-connected cfc graphs with 2n 3 90 ............... 38 Number of unlabeled and labeled cfc with n(G) = 1 ........... 39 vii CHAPTER 1 Introduction Enumeration problems for cubic graphs have been studied by many combinatori- alists and there is a long record of activity in this area by mathematicians and chemists [Ba70]. For a historical perspective the reader can consult [Gr92] for an overview of the last 100 years. Counting cubic graphs was considered a fundamental problem by the chemist A.T. Balaban over 20 years ago [Ba70]. He was able to solve small, special cases by brute force methods. As early as 1959, RC. Read derived formulas for the number of cubic graphs with a specified number of vertices using his superposition theo- rem(See [R59], [R60] and [HPa73]). But these were largely of theoretical importance and not suitable for computation. Later he found a differential equation for counting general cubic graphs [R70] and specialized it for cubic graphs with at most two loops or multiple edges. Then he derived a non-linear, second order differential equation whose solution is the exponential generating function(egf) for a certain class of con- nected cubic graphs. Finally he used the well-known exponential relation between egf’s for graphs and connected graphs to obtain a linear, second order differential equation for cubic graphs. However, he did not provide a recurrence relation for cu- bic graphs or any calculations. Wormald [W790] approached this problem rather differently but he also found a 1 differential equation for counting k—connected cubic graphs for k=0, 1, 2, and 3. For each of these cases he derived a separate recurrence relation. These were used to calculate the number of k-connected cubic graphs of order up to 30 for each k. All of these results appeared in his thesis [W79a]. In a recent related paper, Palmer, Read, and Robinson found a recurrence relation for the number of claw-free cubic graphs [PaRROx]. In their article, they derived a partial differential equation for the egf of labeled general cubic graphs with 3 single edges, d double edges, and l loops by using an edge-deletion operation to derive a second order differential equation whose formal power series solution is an exponen- tial generating function for labeled general cubic graphs. We extract the coefficients of the solution in the form of a recurrence relation which permits calculation. We have used the rasulting relation to calculate numbers of general cubic graphs by con- nectedness. We have applied a computer program in C++ to the recurrence relations and compiled extensive tables. Empirical checking confirms that the small cases are consistent with Balaban’s earlier tables. At the International Graph Theory Conference at Western Michigan University in 1992, MD. Plummer raised several questions about the proportion of claw-free cubic graphs with specified properties. Pahner, Read, and Robinson [PaRROx] used multivariable, exponential generating functions to derive a linear, second order, ho- mogeneous differential equation from which a recurrence relation can be extracted for the number of claw-free cubic graphs. We use the exponential relation between egf’s for graphs and connected graphs to find the number of connected claw-free cubic graphs. The numbers of claw-free cubic graphs by k—connectedness for k = 2, 3 were found by combining the numbers of general cubic graphs and certain formulas found in [MPaRROx]. The final section of the thesis deals with asymtotic results for general cubic graphs. Wormald proved [W79c] that almost all labeled cubic graphs have vertex connectiv- ity n = 3. And in [MPaRROx] it was shown that almost all claw-free cubic graphs have vertex connectivity n = 2. In Chapter 4, we prove that almost all general cubic graphs are 1-connected by using the method of Inclusion and Exclusion with two properties. Furthermore, it is shown that almost all 100pless general cubic graphs are 2-connected. Here are some of the basic definitions we need from graph theory. General graph theoretic terminology and notation which are not included here may be found in the book [CL96]. And the basic knowledge of labeled enumeration techniques can be found in [HPa73]. Let V = {v1, - . - ,vn} be a set of n labeled vertices. And E is a set of unordered pairs of vertices, called edges. A labeled graph G consists of the ordered pair (V, E) of sets of vertices and (single) edgas. If u and v are vertices and the unordered pair av is the edge of G, we write e = no and we say that ”u and v are adjacent” or ” u and v are joined by the edge e” or ” e is incident with u and v ”. We can define a general graph by refining the definition of an edge. If u and v are identical, where e = av, this new type of edge is called a loop. Two distinct vertices joined by two single edges constitute a double edge. If there are three single edges between two distinct vertices, we have a triple edge. A labeled general graph G is a labeled graph which may have single edges, loops, and double edges. The degree of a vertex v, denoted by deg 12, is the number of edges of G incident with v. A graph G is regular of degree r or r-regular if degv = r for each vertex v of G. In particular, if r = 3, it is called 3-regular or cubic. The (vertex) connectivity of a graph G, denoted K.(G), is the cardinality of a smallest subset of vertices of G whose deletion disconnects G or reduces G to a single vertex. Thus the connectivity of a complete graph, K", of order n is n(K,,) = n — 1. And the connectivity of a general cubic graph is 0,1,2 or 3. A graph G is k-connected, if n(G) Z k. Let {run} and {ya} be sequences of real numbers. If there are constants K and N such that lxnl S K ° lynl! for all n > N, we write 23,, = O(yn). If son/y" —> O. as n —-> 00 We write 25,, = o(y,,). If 23,, = (1 + 0(1))yn, we say that xn and yfl are asymptotic equivalent and we write 23,, ~ yn. CHAPTER 2 Computing the number of Labeled General Cubic Graphs 2. 1 Computation In this Chapter, except when otherwise specified, all graphs are labeled general cubic graphs but without triple edges, having exactly 3 single edges, d double edges, and l loops. These cubic graphs with 2n vertices satisfy the relation: 23+4d+2l 2 = n 3 Let G (x, y, 21)) be the exponential generating function G(,wxy, )=,Zg(sdl)z;2ynw 3, dl where g(s, d, l) is the number of labeled general cubic graphs with 3 single edges, d double edgas, and l loops. The first and second order partial derivatives of G (cc, y, w) are denoted in the usual way. For example, G3 is the partial derivative of G (:r, y, w) with respect to 2:. Furthermore G, is the exponential generating function for labeled, general, cubic graphs which are rooted at a single edge but the root edge is not rep- resented by a factor of :13. Palmer, Read, and Robinson [PaRROx] derived a partial differential equation in- volving these egf’s by applying a reduction operation which removes the root edge. This operation is performed on a general cubic graph in the following way. Suppose a and v are the vertices of the root edge. Let ul and U2 be the other neighbors of a, while v1 and 222 are the other neighbors of v. Now we remove from the graph the vertices u and v and edges incident with them. Then we add the new edges ulug and vlvg which will be a part of new root edges. Thus the degrees of u1,u2,v1, and 222 are preserved. However there are many possibilities for the types of new root edges that result. Each of the two new edges could be a single edge, part of a double edge or triple edge, an ordinary loop, or pointless loop depending on how the ver- tices u1,u2,v1, and 212 were originally related(see Figure 2.1). We can have exactly 17 types of new roots which are based on the following operations. Firstly, if a has an incident ordinary loop, we have a pointless root loop after deleting the root edge av from a general cubic graph. Secondly, if a has an incident double edge, we have an ordinary root loop. Thirdly, if a has two incident single edges uul and nag, then we have a single root edge if there was no edge U1U2 originally, a double root edge if there was an edge u1u2 originally, or a triple root edge if there was an double edge ulug originally. But among the new roots, a pointless root loop and a triple root edge are not considered as components of cubic general graphs. Therefore the above operations convert a general cubic graph to a general cubic graph which consist of 2, 4 or 6 vertices less than before. These observations also hold for the other vertex v of the root edge. The egf was found for each of these rooted graphs in [PaRROx]. This xyw Gw 6 x ny x3y wa Table 2.1: Number of general cubic graphs with 2n S 10. 2n 8 d l g(s,d,l) 2n 8 d l g(s,d,l) 2 1 0 2 1 11 0 1 45360 2 ’0 4 I3 4 4 0 6300 3 0 3 4 8 6 3 0 38640 4 2 1 2 12 8 2 0 55860 3 1 1 12 10 l 0 50400 2 2 0 6 12 0 0 19355 6 0 0 1 *5 0 10 945 3 0 6’ 15 6 0 9 12600 4 0 5 60 5 1 8 37800 3 1 4 180 7 0 8 81900 5 0 4 90 6 1 7 415800 4 1 3 540 8 0 7 378000 6 O 3 120 5 2 6 472500 3 2 2 450 7 1 6 2154600 6 5 1 2 540 9 0 6 1426950 7 0 2 195 6 2 5 4006800 4 2 l 720 8 1 5 7560000 6 1 1 360 10 0 5 4420080 8 0 1 180 5 3 4 2116800 3 3 0 120 7 2 4 15176700 5 2 0 270 9 1 4 20487600 7 1 0 180 11 0 4 10873800 9 0 0 70 10 6 3 3 12272400 44’ 0 8 105 8 2 3 35985600 5 0 7 840 10 1 3 42449400 4 1 6 2520 12 0 3 20571600 6 0 6 3080 5 4 2 2853900 5 1 5 15960 7 3 2 28501200 7 0 5 8400 9 2 2 58835700 8 4 2 4 16380 11 1 2 62886600 6 1 4 43680 13 0 2 28351575 8 0 4 20370 6 4 1 8467200 5 2 3 72240 8 3 1 34246800 7 1 3 80640 10 2 1 61160400 9 0 3 38920 12 1 1 59673600 4 3 2 28560 14 0 1 25439400 6 2 2 123480 5 5 0 514080 8 1 2 116760 7 4 0 6690600 10 0 2 52360 9 3 0 18774000 5 3 1 65520 11 2 0 30309300 7 2 1 115920 13 1 0 27480600 9 1 1 111720 15 0 0 11180820 explains the following partial differential equation from [PaRROx]: 2 G. =(%+§+fig2+%fi)0 +(xzw + 1:2)G, + (‘2—4 + $311} + 1:;“)Gy (21) +(yw + 5333)Gw + 5.5-sz + 35G“, . +:z:2yGw + 3”;ny + x3yG'yw + 9;wa. Every non-empty cubic general graph without triple edges must contain at least 0-! :1 one single edge. Therefore we can extract the coefficient of Lfinrfll from both sides of equation (2.1) and obtain the recurrence relation for the number of labeled, general, cubic graphs. The only boundary condition we need here is g(0, 0,0) = 1(Obviously, g(s,d,l) =0ifs < 1, d<0, I <0): g(s,d,l) = g(22n)g(s—1,d,l—2)+ (6:d)(2:)g(s —6,d,l) 12 Zn 90 Zn .?(4).(.-3.._.,.-1).,(6).(._5,d_2,n + 2(3;2) (22”)g(s-2,d,l—1)+}2(ss——4)'(2:)9(3-4’d_1’1) + g(2:)((d+ 1) + 2(s — 5)(d+1))g(s - 541 + 1’1) + 2(d+ 1) (2n)9(3 —4,d+ Ll— 1) + 2:1(271)g(3— 1,d— 1’1) s 2 2 +lg(_l_§+_1)(2:)g(s—3,d—2,l+1)+(s_3:(8—4)(2:)g(s—3,d,l) + 2(3—23(l+1)(2;)g(s—2,d— 1,l+1) +()()_<_>()() + (1+2)s(l+1) (2;)g(s— 1,d—2,l+2). (2.2) This recurrence relation (2.2) was used to calculate the entries in Table 2.1. The program for these calculations was written in C' + + and is available from the author along with all other computational programs. It can be used to find g(s, d, l) for much larger values of 2n. For example, the number g(38,20,36) on 2n = 76 vertices is the 101 10 Table 2.2: Examples for the unimodality with 2n = 10 and s = 5 or s = 6. 2n 8 d l g(s,d,l) 2n 6 d l g(s,d,l) 5 0 10 945 6 0 9 12600 5 1 8 37800 6 1 7 415800 5 2 6 472500 6 2 5 4006800 10 5 3 4 2116800 10 6 3 3 12272400 5 4 2 2853900 6 4 1 8467200 5 5 0 514080 digit number 19941088105475637102309854906877356628850763148517793791612713 004476823750758375443264307300000000000. Apparently, there is no observable pattern for the entries in Table 2.1. However, suppose we fix 2n and s and order the corresponding entries lexicographically with respect to d and I. Then we find the sequence elements are unimodal. For example with 2n = 10 and s = 5 or s = 6, we have the following Table 2.2. We have no explanation for this behavior. Equation (2.1) can be converted to a partial differential equation whose formal solution is the egf for the number of connected, general, cubic graphs by the substi- tution G(x) y) 11)) : 8013.31.10), where G1(:c, y, w) is the egf for connected, general, cubic graphs, z'.e. a: w G1(,=:cy,w) Zgl(s,,)dl 5+:— I . s,,dl ( ) Thus each occurrence in equation (2.1) of G and its partial derivatives is replaced 11 Table 2.3: Number of 1-connected general cubic graphs with 2n 5 10. 2n 8 d 1 91 (8, d, l) 2n 8 d l g1(s, d, l) 2 1 0 2 1 11 0 1 45360 3 0 3 47 4 4 0 5040 2 1 2 12 8 6 3 0 38640 4: 3 1 1 12 8 2 0 55440 2 2 0 6 10 1 0 50400 6 0 0 1 12 0 0 19320 5 0 4 90 9 0 6 529200 4 1 3 360 8 1 5 3175200 6 0 3 120 10 0 5 2630880 3 2 2 360 7 2 4 6804000 5 1 2 540 9 1 4 14288400 6 7 0 2 180 11 0 4 8391600 4 2 1 720 6 3 3 6048000 6 I 1 360 8 2 3 28123200 8 0 1 180 10 1 3 36288000 3 3 0 120 12 0 3 18446400 5 2 0 270 5 4 2 1814400 7 1 0 180 7 3 2 23587200 9 0 0 70 9 2 2 54658800 7 0 5 5040 10 11 1 2 59875200 6 1 4 25200 13 0 2 27442800 8 0 4 15120 6 4 1 7257600 5 2 3 40320 8 3 1 33112800 7 1 3 70560 10 2 1 60328800 9 0 3 33600 12 1 1 59421600 4 3 2 20160 14 0 1 25401600 8 6 2 2 110880 5 5 0 362880 8 1 2 110880 7 4 0 6350400 10 0 2 50400 9 3 0 18522000 5 3 1 60480 11 2 0 30164400 7 2 1 115920 13 1 0 27442800 9 1 1 110880 15 0 0 11166120 12 by a corresponding partial derivative of G1. The result is 2 5 3323/11) 5543/2 w a: (Gl)z_(_2"+'Z'+ 2 + 8) 4 + ($211) + -””—23)(Gl). + 2:4 2753/ (‘2— + $321) + —2—)(G1)y 2 2 4 + (yw + 1})(01)... + 53401)... + mm)... 6 2 (2.3) 1' + x:y(cl)...+ +401)... + res/(GI)... + 2,400.0... :(Gllz (G1): + 35(Gl)x(G1)y + 3323/(Gllz(Gl)w y2 g(GIMGlly + 93 331(31):)(Gllw+ y2(Gllw(GI)w- “Jaime As we did for equation (2.1), we can find the recurrence relation for the numbers of connected, general, cubic graphs by extracting the coefficient of T”),— from both sides of (2.3). The relation is supported by the boundary conditions 91(1,0,2) = 1,gl(6,0,0) = 1,gl(3,1, 1) = 12, and g1(5,2,0) = 270: gl(s,d,l) = 2(38" 2) (2n)gl(s — 2,d,l — 1) + M639,“ — 4,d— 1,1) 2 s 4 + (d+1)(1:—2(s - 5)) (2;)gl(s _ 5,d+ 1,1) 2(d+ 1) 2n 12d 2n 3 (2)gl(s—4,d+1,l—1)+—s-(4)gl(s—6,d,l) +-:-l(2;)gl(s—1,d—1,l)+l2—(l;—1)(2:)gl(s—3,d—2,l+1) +(.9—3)(.sr—4) 2 s—3,d,l) 2n)91( 22)m( 3 +2(3_2)(l+1) s—2,d—1,l+1) ( + (d+1)3d+2)(22")gl(3_7,d+2,l) ( + ——2d(ls+ l) (22”)91 s — 4, d,l + 1) + (l+1)(l+ 2) (2n s 2)g1(s—1,d—2,l+2) (2.4) 13 +(2n)!’§‘"igl(i,j.k)(s—3 —z')gl(s—3 3-z'd— j,l—kl 28 (mid, k)!° (ms-3— —i ,d-j,-l k)! i,j,k + (2n)!”$9913j,k)(d+1—j)gl(s—4—zzd+1art—k) 3 my): (7711.330! ' (ma—S—i,d+l—j,l—k)! s—2,d—1,l+1 Z 391(Z,j,k)(l+1—k)gl(S—2—2,d—1—j,l+1—k) (mij,k)! ' (ma—2—i,d-1—j,l+l—k)! + (2n)! 8 £ch +(_22" 3)" 7215211910 3”“ )(d+2-j)91(3—7—i,d+2—j,l—k) i,j,k (mini)! ' (ms-7-i,d+2-j,l_k)l +(___.'2n)g 3-§+1 jgl( z" j,k)(l+1— k)91(8 _ 4 _ i,d—j,l + 1 _ k) i,j, k (miJ.k)! ' (ms-4—i,d-j,l+1—k)l s— 1 ,-d 2,l+2 (2n)! 2: kg1(i,j,k)(l + 2 — k)gl(s -1-—i,d— 2 -j,l + 2 — k) 23 (mi,j,k)! ' (ms-l-i,d—2—j,l+2—k)! + 3,331: Where mfg" k: 2i+43 +2]: Formula 2.4 does not lend itself to the integer programming mode of C + + so the entries in Table 2.3 were calculated from equation 2.4 using Mathematica. The program was too slow to compute values beyond 2n = 12. Note that there are values of s, d, and l for which g(s,d, 1) ¢ 0 but gl(s,d, l) = 0. The first of these in Table 2.1 is g(2,0,4) = 3 whereas 91(2,0, 4) = 0 in 2.3. In general, 2 ! g(n,0,2n) = (2:2. and gl(n,0,2n) = 0. The reader will notice in Table 2.3 that some of the entries are identical. For example, g1(6, 2, 2), g1(8, 1,2), 91(9,1,1) have exactly the same value, namely 110880. We believe that these coincidences are accidental, zle they are not explained by any natural bijection. In consulting Balaban’s Table 1d(p.471 of [Ba70]) one finds the diagrams of the unlabeled general cubic graphs that contribute to the entries of value 110880 in our Table 2.3. There are exactly 6 graphs of order 8 in each category and the orders of the automorphism groups in each category are 1, 2, 2, 4, 4, 4. To explain why g1(8, 1, 2) = g1(9,1, 1) we could try to define an automorphism preserving operation 14 that converts two loops at u and v to a single loop. This might be accomplished by identifying the two loop vertices discarding the loops, and then attaching a new edge with a new loop to the vertex u(= v). The reader can verify that this operation converts all but one graph with parameters 3 = 8, d = 1, l = 2 to a graph with parameters 3 = 9, d = 1, l = 1. The graph where two loops have a common neighbor will be converted to a graph with not one but two double edges. To explain why gl (6, 2, 2) = g1(8, 1, 2) we could try to define an operation that converts two double edge to one. But again no such operation seems to be satisfactory. 2.2 2-connected general cubic graphs To find the numbers of 2-connected general cubic graphs, we use an approach different from that of precious sections. Following Wormald [W79c] we begin with general graphs which are cubic except for one or two vertices of degree 2. Since we modify and extend Wormald’s method for cubic graphs to general cubic graphs, we will use his terminology. A closely general cubic graph is a graph in which just one vertex is of degree 2 and the rest are of degree 3. A fairly general cubic graph is a graph in which two vertices are of degree 2 and the rest are of degree 3. A almost general cubic graph is a fairly general cubic graph in which the two vertices of degree 2 are non-adjacent. A special almost general cubic graph is an almost general cubic graph which is not 2-connected but becomes 2—connected after joining the two vertices of degree two. A network is a graph in which two vertices are distinguished as positive pole and negative pole denoted (+) and (—). A special almost general cubic network is an special almost general cubic graph in which the two vertices of degree 2 are distinguished as a positive pole and a negative pole. An almost general cubic network and a fairly general cubic network are defined similarly(see Figure 2.2). 15 A1328 A+V 5m? #83qu £92m 05:0 3:3 365% UBQQERTN «€an 033 :88? .805» .Alv EB A+v £3, 5.5332 23an 05:0 H88? 1228» Buoogoolm AIV To 3 1%3 €me 033 £830 Ego—How guacamoolm ’ 2a 033 baa 1:28» VA .3 .1 +V Figure 2.1: 16 Let 02(2), y) be the egf G (x y) 2:9 (s cum—”yd 2 1 = 2 1 and (Zn)! where 92(3, d) is the number of 2-connected labeled general cubic graphs with 3 single 28+4d 3 . The loop parameter is absent here because, edges, d double edges and 2n = obviously, 2-connected general cubic graphs has no loops. Let C(z, y) be the egf for the number, say c(s, d), of 2—connected general closely cubic graphs, where 2n — 1 = W. Let F(:L', y) be the egf for the number, say f (s,d), of 2-connected general fairly cubic graphs, where 2n = W. Let A(:c,y) be the egf for the number, say a(s, d), of 2-connected general almost cubic graphs, where 2n = W. And let B(a:,y) be the egf for the number, say b(s,d), of special almost general cubic networks, where 2n = W. Therefore the corresponding egf for special almost general cubic graphs is B (x, y) / 2. The corresponding egf’s for almost general cubic networks and fairly general cubic networks are 2A(a:, y) and 2F(:z:, y), respectively. The next task is to find five relationships among the numbers of the graphs above and derive a recurrence relation for the number g2(s, d) of general cubic graphs. We begin with definitions of some basic graph operations that are useful in relating the types of graphs mentioned above. The removal of a vertex from a graph is a operation which removes the vertex and all incident edges. The suppression of a vertex v of degree 2 consists of removing v and joining the two vertices formerly adjacent to v by a new edge. The first and simplest operation on a graph in order to find the first relationship is removing a single edge from a 2-connected general cubic graph, which produces a 2-connected almost general cubic graph or a special almost general cubic graph. Because deleting one edge might produce connectivity 1 graph(see Figure 2.3). There are 3 single edges in a general cubic graph, hence there are 3 possibilities to remove 17 Figure 2.2: 2-connectcd 2-connected l-VI 7 III, root a(s-l, d) s g(s,d) Connectivity 1. .11 b(s-l, d)/2 each single edge. Hence we have s . 92(8,d) = a(s -—1,d)+ b(s —1,d)/2. Equivalently, (G2),, = A + B/2. (2.5) The removal operation for a vertex of degree 2 of a 2-connected closely general cubic graph producas two vertices of degree 2(see Figure 2.4). That means we can have a 2-connected fairly general cubic graph if the obtained graph is still 2-connected, or a special almost general cubic graph if the obtained graph has connectivity 1. But there is an extra term we need, because a 2-connected closely general cubic graph which has 1 double edge and 2 single edges on 3 vertices (following Read [R70] we call this a trumpet) can be converted into a graph with 1 double edge on 2 vertices. And this graph does not belong to any category of graphs we mentioned above(see Figure 2.4). This operation can be considered inversely as adding a new vertex to a 2-connected fairly general cubic graph or a special almost general cubic graph to 18 Figure 2.3: 2-connected 2 connected \fl f(s 2 d) Connectivity l b(s-2,d)/2 produce (2n — 1) closely general cubic graphs. Therefore we have c(s,d) = (2n —1)f(s — 2, d) + (2n —1)b(s — 2.d)/2, for (s, d) 7e (2,1). Then the relationship between the number of these graphs in egf form is C— — x2F +— 2 —B + 1:3], (2.6) where the egf 1;! is for the trumpet. The next task is to find the relationship between the 2-connected fairly general cubic graphs and other graphs(see Figure 2.5). The 2-connected fairly cubic graph consists of 2-connected almost general cubic graphs and the graphs which have the 2 vertices of degree 2 that are adjacent to each other. In case of the 2-connected almost general cubic graphs, we don’t do any operation on it. From the other 2-connected fairly general cubic graphs which have 2 vertices of degree 2 that are adjacent to each other, we remove these two vertices with incident edges. Then the graph is converted into a 2-connected fairly general cubic graph or a special almost general cubic graph depending on their connectivity. Again here we have to consider extra term, that is 19 Figure 2.4: 2-connected 2- connected a(s. d) a(s d) 2 connected f(s- 3. d) Connectivity l. ' O I I x‘y/2\_. + b(s- 3 ,d)/2 a fairly general cubic graph which consists of 3 single edges and 1 double edge on 4 vertices. It has a egf 1:3y/ 2. But the removal of two vertices of degree 2 reduces the the number of single edge by 3. Hence we have f(s,d) = a(3,0!) + f(3 - 3,11) + b(3 - 3,d)/2, for (s,d) # (3,1). Then the relationship between the number of these graphs in egf form is F: A + x3F + -2—B + —:—xy. (2.7) Next we will convert 2-connected almost general cubic networks to 2-connected closely cubic graphs or 2-connected fairly general cubic networks(see Figure 2.6). If the positive pole (+) in a 2-connected almost general cubic network is not in a 3- cycle, the suppression operation gives us a 2-connected closely general cubic graph with exactly one less single edge and the same number of double edges. Suppose the positive pole (+) is in a 3-cycle with two adjacent vertices, say a and b and (+) is the only vertex which is adjacent to both of them. By removing the vertices (+), a and b, we have a graph which has two vertices, say c and d, of degree 2, which were 20 Figure 2.5: 2-connected 2-connected a ‘\ a <- + > - G ——. A b b / 23(s. d) 2f(s-3, d) adjacent to a and b, respectively. Now adding a new positive pole (+) to this graph by joining this new vertex to c and d results in a 2-connected fairly general cubic network. But if (+) is not the only vertex adjacent to both a and b, then the negative pole (—) must be the other one. Hence the network must have (s,d) = (5,0) and there are exactly 12 of these. Therefore these graphs contribute x5 / 2 to the egf for 2A. Collecting these observations we have 2 - a(s,d) = 2n(s — 3)c(s — 1,d) + 2n(2n —1)2-f(s — 3,d), for (s,d) ¢ (5,0). But the egf for 2A is 5 2 - A = 2:20,, — 2330 + 2:133F + 5%. (2.8) To find the relationship between special almost cubic networks and the other graphs, consider a special almost cubic network as a sequence of at least two blocks say G1, - - - ,Gk for some integer k. It is possible to consider as a sequence of blocks, because this graph should be 2—connected after joining the two poles(see Figure 2.7). 21 Figure 2.6: Special almost cubic Network 1 2 i 2k 2k+1 .................. K2 K2 A sequence of (at least ) two Block. The block G1 contains the positive pole, and the block G), contains the negative pole. The intersection of each pair of consecutive blocks is a cut vertex. Except for the poles all other vertices have degree 3. Hence all cut vertices v, have degree 3, so their neighbors lie in consecutive blocks, G.- and Gm. That means the cut vertex 11,- may be of degree two in G,- and of degree one in G.-+1 or vice versa. But if v,- is of degree one in G.-, then G,- should be isomorphic to K 2. Otherwise, it is not a block any more. Therefore, we can conclude the G23 are isomorphic to K 2 if i is even, and the G.- are 2-connected fairly general cubic graphs if i is odd. It should be odd(see [W79d]). In all, the egf of a special cubic graph is the product of each egf of the blocks G, for i = 0, ~ -- , k, because they do not share any edge or double edge. There are two possibility of position of each block of a fairly general cubic graph(or can be considered as a network), so the egf of G, when i is odd is 2F. But G,- when i is odd might be the graph with 1 double edge on 2 vertices, and it does not belong to any catagory of our graphs. So we have to add the monomial of this graph to the egf of the fairly general cubic networks, that is 2F + y. Let G1, - - - ,ngH be the sequence of blocks for a special general cubic graph with 219 cut vertices. Then the egf of this graph is [@F+ynV@F+y) 22 where :1: / 2 is the egf of K2 graph. It follows that °° 2F+ y)2 B = 2F + k+l . k = $( . k=1( y) :1: 1 — :1:(2F + y) The system of five equations above( (2.5) to (2.9)) can be solved for 02. We find: (G2). = 911—453(00402)... + (22:4 — 42:7 + 2310 + 2353/ - 223731) (6'2) + (8:1:4 + 42:7) 4 m 4 + (161:3 - 12:1:6 —— 22:9 + 21:12 + 4mg — 43431 + 162273;) 4 (2.9) (G2)2(G2)x (02): (2.10) 1 3 3 1 3 9 3 1 +sz_ 138+.qu __ Z$14+§$6y_Zz9y+Zx12y+§$y2 7 1 _ $4312 + 1x73}? __ 59:10:12. As usual we can find the recurrence relation for the numbers of 2-connected, general, cubic graphs by extracting the coefficient of at; from both sides of equation (2.10) af- ter multiplying by :c. The relation is supported by the boundary conditions 92(6, 0) = 1, g2(9,0) = 70, 92(12,0) = 19320, 92(15,0) = 11052720, 92(7, 1) = 180, 92(10, 1) 45360, 92(13,1) = 24948000, 92(22) = 6, 925,2) = 130, 92(8,2) = 45360, and 92(13, 1) = 24494400: 943. d) = £91) (2;)920 — 3. d) — 333—1916;)920 — 6,4) __ 360(:— 9) (2:) 92(3 _ 9,61) + 20160(s — 12) (2812) 92(3 _ 12,d) + 2(3; 1)(2;)gg(s—1,d— 1) — #6:)943—40— 1) +w<2:)gg(s—7,d— 1) — @(2:)gg(s— 10,d— 1) + (s — 3)(8 - 4) (22”)92(s _ 3, d) _ 24(3 - 6)(S - 7) (2:)g2(3 _ 6, d) + 360(3 — 9)(s — 10) (2:) 92(3 _ 9, d) + 12(3 - 4)(s - 5) (24") 92(3 _ 4, d _1) _ 360(3 —:)(3 — 8) (2:) 92(3 _ 7,d _ 1) (2.11) 23 23:" £920.00 — 3 — z‘)g2(s — 3 - .-, d — j) 2(2n)! + (mu)! ' (m._3_.-,d—j)! 3 .. w (2n)! “‘6'digz(z',j)(s - 6 — 0920 - 6 - zyd — j) + 3 a: (mid)! ' (ma-G-i,d—j)! (_2_n_)! ’_3’digg(i,j)(s — 3 — i)(s — 4 — i)gg(s — 3 —— 2', d — j) + 3 2 (mid)! ' (ms—3-520! _ (2_n)_!.:6’d 292(i,j)(8 — 6 _i)(3 _ 7 — i)g2(s — 6 _ i,d— j) 3 (mid)! ' (ms—G—i.d—j)! M where mm- = ”—3411. Formula (2.11) also does not lend itself to the integer programming mode of C + + and so the entries in Table 2.4 were calculated from 2.11 using Mathematica. Note that in Table 2.4 we have g2(8,2) = 92(10,1) = 45360. On examining the diagram in Balaban’s Table 1d(p.471 of [Ba70]), we conclude again that this coinci~ dence is accidental. Clearly a 3-connected general cubic graph cannot contain double edges. Therefore 3-connected general cubic graphs are precisely the 3-connected cubic graphs. An equa- tion with an egf solution for 3-connected cubic graphs was found by Wormald [W79b] and [W790]. The recurrence relation for the number, say 93(n), of 3-connected cubic graphs is 2 rn = (3n — 2)(r,,_1 + E13434) i=2 L222 3,12,, rn and with boundary condition r2 = 1. Tables are can be found where g3(n) = in [W 79a]. 2.3 Conclusion The chemist, A.T. Balaban [Ba70] found all of the connected unlabeled general cubic graphs of order less than 12 by constructive methods. He included both tables and 24 Table 2.4: Number of 2-connected general cubic graphs with 2n _<_ 12. 2n 8 d 92(s,d) 2n 3 d 92(s,d) 4 2 2 6 7 4 3628800 6 0 1 10 9 3 13003200 3 3 120 11 2 24494400 6 5 2 180 13 1 24928000 7 1 180 15 0 11052720 9 0 70 6 6 39916800 4 4 5040 8 5 718502400 6 3 23520 10 4 4340952000 8 8 2 45360 12 12 3 13571712000 10 1 45360 14 2 24638644800 12 0 19320 16 1 25177521600 10 5 5 36288(T 18 0 11408720400 Figure 2.7: fi—s —0 Oh diagrams for these graphs in his paper. But there is no known recurrence relation for the numbers. We verified the numbers of labeled k-connected general cubic graphs in Tables 2 and 3 for k = 1, and 2 and 2n 5 8 by computing the order of the automorphisim groups of the corresponding configurations in Balaban’s collection of diagrams. We found only one flawed diagram. On page 471 of [Ba70] there should be 3 diagrams of connected general cubic graphs with 3 loops and no double edges. The left-most diagram is incorrect and one loop should be eliminated. There is also another incorrect statement in [Ba70] that ought to be mentioned. Let ugl(s, d, I) be the number of connected, unlabeled, general cubic graphs with 3 single edges, d double edges, and l loops on 2n = (2.9 + 4d + 21)/ 3 vertices. Balaban 25 Figure 2.8: Qéi — @ Operation 1. Operationz. asserted that for all n 2 3: ug1(s, 1,0) = ugl(s,0, 2). (2.12) But we find that equation (2.12) is not true for Zn 2 12. In his paper, he defined a correspondence between connected unlabeled graphs with one double edge and connected graphs with exactly two loops by an operation which makes a double edge into two loops (see Figure 2.8). But for Zn _>_ 12, an unlabeled graph might be converted to a disconnected graph with two loops. Obviously this is also not true for the case of labeled graphs. For example, we found following by using recurrence relation (2.4): 91(16, 1, O) = 27407872800 79 27392904000 = 91(16, 0, 2). Balaban did discover the following useful identity. Theorem 2.1 (Balaban) Ifn 2 2 is fixed, 2n = (2s + 4d+ 2l)/3 and ugl(s,d,l) is defined as above, then 2 ugl(s, d, 0) = Z ug1(s, 0, l). d 1 The 1 —1 correspondence which proves the theorem is indicated in Figure 2.9. Note that the identity also holds for labeled graphs because the number of automorphisms is preserved by the operations used in the correspondence. We also verified our 26 resulting numbers for the k-connected general cubic graphs when d = 0 and l = 0 by the tables in [W79a]. Palmer, Read, and Robinson [PaRROx] counted labeled, claw-free cubic graphs by using expansion and dilation operations. Our results together with [MPaRROx] will be used to find the number of k-connected claw-free cubic graphs for k = 1,2, and 3. We also plan to investgate the enumeration problem for 4-regular general graphs with given Ire-connectedness for k = 0, 1, 2, 3 and 4 (see [RW80]). 27 CHAPTER 3 Computing the number of Claw-free Cubic Graphs with given Connectivity A claw-free cubic graph G is a cubic graph which contains no induced subgraph isomorphic to K13. Therefore these are precisely the cubic graphs whose vertices all belong to triangles. For convenience we refer to them as cfc’s. For a study of the history of the enumeration of regular graphs the reader can consult Gropp [Gr92]. In [PaRROx] Palmer, Read, and Robinson studied claw-free cubic graphs and computed the number of claw-free cubic graphs with up to 52 vertices. Moreover, their paper contained a partial differential equation for the exponential generating function(egf) of labeled, general cubic graphs. In Chapter 2 this equation was used to derive recurrence relations for general cubic graphs with a specified number of multiple edges and loops by connectedness. There is another relevant paper with enumeration formulae for cfc’s, namely [MPaRROx]. Combining results of these papers makes it possible to count claw-free cubic graphs with given connectivity. In the present work, we will follow the terminology and method in [PaRROx] to 28 find the number of k-connected claw-free cubic graphs where k = 1, 2, and 3. In a claw-free cubic graph, every vertex belongs to a triangle. The maximum number of triangles in which a vertex may lie is 3. Clearly, a vertex lies in 3 triangles if and only if it is a vertex of K4. A diamond in a cfc is an induced subgraph isomorphic to K, — e. A vertex lies in exactly two triangles if and only if it is one of the vertices of degree 3 in a diamond. A string of diamonds is a induced subgraph in which diamonds are adjacent in series. A ring of diamonds is a connected component in which every vertex belongs to a diamond. In [PaRROx] there are two important operations which convert general cubic graphs to claw-free cubic graphs. One of them is the expansion operation which converts an edge of a general cubic graph to a string of diamonds. The inverse oper- ation to expansion is called reduction. The other operation is dilation which inflates a vertex of a general cubic graph to a triangle. The inverse operation to dilation is called contraction. Consider a cfc with no component isomorphic to K, or a ring of diamonds. The reduction operation applied to all strings of diamonds in this cfc results in a general cubic graph with no loops but possibly some double edges. The two vertices of such a double edge are mutually adjacent to a third vertex. These vertices constitute a trumpet. Still, every vertex must belong to a triangle. Note that if e is an edge caused by a reduction, then such a triangle must be part of a trumpet in which e is a multiple edge. Now the contraction operation completes the conversion from claw-free cubic graphs to general cubic graphs. 3.1 Connected claw-free cubic graphs We define oo H(z) = Z hum. n=0 where h" is the number of labeled claw-free cubic graphs on 2n vertices. Then H (22) 29 Table 3.1: Boundary conditions. 111(1) = 0 mm = 13621608000 mm = 12 h1(8) = 8009505504000 211(3) = 60 121(9) = 3123380227968000 h1 (4) = 2520 h1(10) = 1832279324908032000 111(5) = 453600 h1( 11) = 2054813830468439040000 6l (6) = 59875200 111(12): 1665031453088810526720000 is the exponential generating function for these graphs. By applying expansion and dilation operations, Palmer, Read, and Robinson [PaRROx] derived the following differential equation whose formal power series solution is the egf for labeled claw- free cubic graphs on 2n vertices: 0 = (1442.8 + 28827 — 57624)H"(z) + (—36210 — 9629 + 2428 + 144.27 + 57626 + 38425 — 57624 — 288023 — 57622 + 1152)H’(z) (3-1) + (—15211 — 742.10 — 13029 — 9628 + 14427 + 36826 + 33625 — 28824 — 24023 — 28822 — 96z)H(z). Equation (3.1) can be converted to a differential equation whose formal solution is the egf for the number of connected, claw-free cubic graphs by the substitution H(z) = elm”), (3.2) where H1(z2) is the egf for connected, claw-free cubic graphs, i.e. 111(2) = Zh1(n)(2::)!, n=0 and h1(n) is the number of connected, labeled cfc graphs with 2n vertices. After substitution in equation (3.1) of H (z) and its derivatives from equation (3.2), we have the following differential equation for H1(z): 30 I 0 = (1442:8 + 28827 — 57624)H;(z)H,(z) + (14428 + 288::7 — 57624)H;'(z) + (—36210 — 9629 + 2428 + 14427 + 57626 + 38425 3 3 — 57624 — 288023 -— 57622 + 1152)H;(z) ( . ) + (—15.z11 — 74-210 — 13029 — 9628 + 14427 + 36826 + 33625 — 28824 — 240;:3 — 28822 — 962). The recurrence relation for the number of connected, claw-free cubic graphs can be found by multiplying (3.3) by z and extracting the coefficient of (7‘3? The rela- tion (3.4) is supported by the boundary conditions in Table 3.1: For n _>_ 13, we have: (2n)! “‘7 kh1(k)(n — 7 — k)h1(n — 7 — k) 1152n Z (2k)!(2n — 14 — 2k)! 88(2n)! :kh1(k)—(n 6— k)h1(n— 6— k) hl (n) = — 144 8872,1152 (2k)!(2n—12—2k)! (2n)! "—3kh1(k)(n— 3— k)h1(n— 3— 1:) ”76115212: (2k)!(2n— 6— 2k)! (2n)! (1152n)(2n — 14)'(n "7)(71 — 8)h1 (n — 7) (2”)' (3.4) — 144 _ 288(1152n)(2n -— 12)! (n — 6X" — WM" _ 6) + 576(1152T(3?2)7:_ 6)!(n - 3)(n — 4)h1(n —- 3) (270' + 36(1152n)(2n— 20)! ,n( 10)h1(n _ 10) (2n)! + 96(1152n)(2n — 18)!(” — WM" _ 9) — 24 (2")! (n — 8)h1(n — 8) (1152n)(2n — 16)! 31 (2n)! — 144 (1152n)(2n — 14) !(n — 7)h1(n — 7) _ 576(1152n()2(123: — 12)! (n _ WM" — 6) — 384(1152n()2(7222! - 10)! (n — “WM" _ 5) + 576(115238; __ 8)! (n — 4)h1(n — 4) + 2880(1152£:?2);_ 6)! (n — 3)h1(n — 3) + 576 (2")! (n — 2)h1(n — 2). (1152n)(2n — 4)! By applying Mathematica to this recurrence relation, we calculated the numbers of 1-connected cfc graphs shown in Table 3.2. Actually the boundary conditions are found by using the equations (3.3) and (3.4). In order to find the values in Table 3.1, we have to add the contribution from the constants in equation (3.3) to the values which come from the output of the above recurrence relation (3.4) for n up to 12. For example, when n = 12 the number 15 :1: 24! / ( 1152 * 12) = 673229602575129600000 comes from the constants in equation (3.3) and the value 1664358223486235397120000 comes from the recurrence relation (3.4) by using the previous boundary values for n < 12. The sum of these two numbers gives us the boundary condition h1(12) = 1665031453088810526720000. 3.2 2-connected Claw-free cubic graphs A 2-connected general cubic graph can be converted to a 2-connected cfc graph by the expansion operation, which converts an edge of a general cubic graph to a string of diamonds, and the dilation operation, which inflates a vertex of a general cubic graph to a triangle. The smallest 2-connected general cubic graph is K 4. By the 32 Table 3.2: Number of 1-connected cfc graphs with 2n S 60. COWKJOSU‘hOONr—Ib NHHHHHHHHHH OCDOOKIOSCfluh-wtoi—to N H [ONION 01150910 WNNMN O‘Dmflm 1 (n) 0 1 60 2520 453600 59875200 13621608000 8009505504000 3123380227968000 1832279324908032000 2054813830468439040000 1665031453088810526720000 1925086583971531588608000000 3552833935369312965955584000000 5046746501122027301952608256000000 9861817424365745824355502612480000000 27365975784025025428617030645350400000000 61323963707903030791402423349300428800000000 183552463622453002911375211047071799705600000000 720052647634369560568722076458423100794470400000000 2368360586025317757755816851785727694336557056000000000 10146784583491669585186721242630185440440056545280000000000 53795556323350118084055188978516784012472039393198080000000000 246424470779562683529001284375203235733354613795916349440000000000 14384540002844430722123935722367258372736488532009784705024000000000 00 99585626913423785914887522929081920122867390538001130895441920000000 00000 61040547368069278457139458365973168239583736999460339219244777472000 000000000 46763587708656896789988944665808439580376015582411036159102127439872 0000000000000 41141634055363776663530319633729522624244890505593059232232304816003 48160000000000000 32697533978263237827530129558757067499130106959793034875270154251141 20388608000000000000 33 dilation operation K4 is converted to a 2—connected cfc graph of order 12. Therefore these operations produce 2-connected cfc graphs of order at least 12. However, there are 2-connected cfc graphs that can not be produced in this way. In fact there are three types of such graphs: (a) The triangular prism of order 2n = 6. (b) The rings of two or more diamonds of order 2n 2 8. (c) The graphs of order 2n 2 10 obtained by expanding with diamonds the edges of the triangular prism that do not belong to a triangle. Next we need the egf’s for these three families. Of course, K4 is counted by 22/ 4!. The rings of diamonds are counted by °° 22'” 22 1 = -— - —l 1 — 2 2 O C "2.; 2mm 4 2 "( Z / ) (3 5) And 2-connected cfc graphs obtained by expanding with diamonds the edges of the triangular prism that do not belong to a triangle has egf 23b3/12 where Mr) = 2(3): = (1 — 2.2/2)-. (3.6) :0 is the egf of the strings of diamonds. Let @(22) be the egf of all three types above. Then °° 22’" oo (’6 + 1 k + 2 2:2"+3 42(2) “72“sz?” +2 3: ) 2;. . m=2 k=0 L81? G2($, y) be the egf G (a: ) = E (2m d)-—8! 2 7y 8 92 , (2 )! where 92(2m, d) is the number of 2-connected labeled general cubic graphs of order 2m with 3 single edges, (1 double edges and 2m = 3%4—‘1. We define f2(2n, d) to be the 34 number of cfc’s of order 2n built from 2-connected general cubic graphs with 3 single edges, (1 double edges and no loops by dilating vertices and expanding edges. Then we have the following formula which is simpler then the one in [MPaRROx] because we do not have loops in 2-connected cfc’s. Lemma 3.1 For fixed n, d, we have z<>u<<>> <> mi (3.7) where j is the number of diamonds and 2n 2 12. PROOF. Suppose G’ is a 2-connected labeled general cubic graphs counted by g2(2m, d). First we choose 6m labels from 2n available and arrange them in 2m unordered groups of three each for triangles. Then ()E—B is the number of ways to do this. In triangles, the number of ways to label the vertices according to the adjacencies is (3!)2m—2d(32 . 2)d. Since there are 3m original edges in the 2-connected labeled general cubic graph G, they can be expanded by j diamonds using combinations with repetition. We find that the number of ways to do this is ((3‘)) = (BM/"1)- The number of ways to arrange the remaining labels for the diamonds and the number of ways to assign labels to individual diamonds is (4, 4’ , 4) (41/2)J'. 35 [3 Note that the number of 2-connected cfc graphs which can be obtained by (3.7) depends on the number of double edges in 2-connected labeled general cubic graphs 92(2m, d) which were already computed in chapter 2. Define 32(22) = Enema—37 n=0 be the egf of 2-connected cfc graphs which can be obtained by (3.7), then b2(2n) = 2d f2(2n, d)- L913 Z213 H2022) = Z h2(n)(—2-T-l—)—! n=0 be the egf of 2—connected cfc graphs. Then we have H2(22) = 82(22) + @(22). But computing the number of 2-connected cfc graphs by using this egf is not quite so simple. To get b2(2n), we need to compute the number f2(2n,d) and sum up according to the number of vertices 2n and then extract the coefficients of the three egf’s in @(22). By adding, finally, the above numbers from each egf according to the number of vertices, we have the numbers of 2-connected cfc graphs as in Table 3.3. 3.3 3-connected Claw-free cubic graphs Let G3(:r, y) be the egf 03(2) = gasemn—fffi where 93(2m) is the number of 3-connected labeled general cubic graphs of order 2m with .9 single edges and 2m = 35". Then we define f3(2n) to be the number of cfc’s of order 2n built by dilating vertices in general cubic graphs with 3 single edges, no double edges and no loops. Suppose G is a 3-connected labeled general cubic graph counted by 93(2m). Then the contribution of G to f3(2n), with (2m) - 3 = 2n, is 36 Table 3.3: Number of 2-connected cfc graphs with 2n 3 36. n hgcn) 2 1 3 60 4 2520 5 453600 6 59875200 7 10897286400 8 6701831136000 9 2623194782208000 10 1338096104497152000 11 1633313557551836160000 12 1324107982344764897280000 13 1408369399403068118016000000 14 2818005386051236981856256000000 15 3984871608553561924638375936000000 16 7418092561827244386962686894080000000 17 22027134615845465196052794703872000000000 18 49003622223231250364949254126429798400000000 determined by arranging the Zn labels in 2m unordered groups of three vertices each for triangles. Here is the simple relationship between f3(2n) and 93(2m). Lemma 3.2 For fixed n, we have (6m)' f3(2n)= 93(2m)(——2m )!, where 2n = 6m. The smallest 3-connected general cubic graph is K 4. Therefore the dilation operation produces 3—connected cfc graphs of order at least 12. It will produce every 3—connected cfc graph except the triangular prism of order 2n = 6. The numbers 93(2m) can be found by using Wormald’s recurrence relation [W79c]. We have 93(2m)= (2m)‘——— 37:23, where W() wm— mo(m —n+§)n)Mm—n em i=2 37 Table 3.4: Number of 3-connected cfc graphs with 2n S 90. 42 45 12301? 1 60 19958400 622452999168000 258520167388849766400000 675289572271869736778268672000000 7393367369949286697176489031997849600000000 262780050460968318524397140574168804564664320000000000 25427675465852111040703353545981158863084030467978035200000000000 58889957183069494200026410510881160707015095883270060477775872000 00000000000 29580432542192562633088212768260655861143184058859525620680851009 83678402560000000000000 29808901529190080191091868785898157902251888443560315850689944728 85037078284530089984000000000000000 56567777202660270057311888745430002232548201516818735491474839068 96091164814511454342829299466240000000000000000 19180389783750869957819747472171834680204611113499325001254426931 263286095897879381918156143781281083162624000000000000000000 11115915392542298567239161105083018964835040519190496510868967479 34939649957201714150533128051831216937487176742993920000000000000 00000000 10600575980644016126749004203059170007101469467195376858944976266 33654849683785877426968779460035111370065575453993044941123616768 000000000000000000000 We used this method to compute the numbers 93(2m), i.e., the number of 3-connected cfc graphs, shown in 3.4. This completes the enumeration of cfc graphs with given connectivity. 3.4 Conclusion The values of h1 (n) and h3(n) were checked for n 5 12 by calculating the order of the automorphism of graphs of the small connected cfc’s. of the unlabeled cfc’s with connectivity 1. These are the graphs that contribute The numbers h2(n) were also checked for small values of n by finding the diagrams 38 to the difference between h1(n) and h2(n). For example, there are 20 unlabeled cfc’s with 2n = 24 vertices and K(G) = 1. And the number of ways to label these is 340923470744045629440000. Then we compare this to the number which is the Table 3.5: Number of unlabeled and labeled cfc with 19(0) 2 1 2n # of unlabeled cfc with K(G) = 1 # of 13])eled cfc with 79(0) 2 1 14 1 2724321600 16 1 1307674368000 18 3 500185445760000 20 5 494183220410880000 22 11 421500272916602880000 24 20 340923470744045629440000 difference between h1(12) and h2(12), which are found in the Tables 3.2 and 3.3, respectively as follows: 340923470744045629440000 = h1(12) - h2(12) The numbers on the right side of the Table 3.5 are exactly the differences between h (n) and h2(n). Finally, we note that almost 80% of cfc’s are 2-connected when the number of vertices is 34 or 36. This is consistent with the observation in [MPaRROx] that almost all cfc’s are 2-connected. 39 CHAPTER 4 Asymptotic number of General Cubic Graphs In this chapter it is convienient to denote the number of general cubic graphs of order 2n with l loops and d double edges by g(2n, l, d). This notation is redundant because we used g(s, l, d) in Chapter 2. In [MPaRROx], the following asymptotic estimate was stated: For I, d = o(\/n) e‘2 (6n)! .2’-2d (302a 23"-(3n)! l!-d!' The authors mentioned that it can be derived directly by the method of inclusion g(2n,l,d) = (1+ 0(1)) (4.1) and exclusion but they did not provide any proof. Here we will derive the formula in all detail by using inclusion and exclusion on two types of properties. Moreover, the equation (4.1) above can be used to find the total number of general cubic graphs with 2n vertices by summing up the terms for loops and double edges from 0 to infinity: g(2n) = (1+ 0(1)) (332" . 235378;». (4.2) Wormald first derived (4.2) in [VV79a] by estimating the number of matrices with given row and column sums. It could also be obtained from matrix approximations of Bender and Canfield [BeC78]. We assume the basic terminology developed in [Pa85] for inclusion and exclusion. 40 4.1 Inclusion and Exclusion for two types of properties Let U be the universal set of 3,, elements, and suppose that Al, - - . ,A, and BI, - - - ,8, are subsets of U. The complement of a set 0 of U is denoted by 0. And for any number k, [k] denotes the set {1,2, - - - ,k}. For I = 0 to s and d = 0 to t, define Sz,d=Z|nAgnnle, (4.3) £61 jEJ where the sum is over all l-subsets I C [s] and d-subsets J C [t]. Now for l = 0 to s and d = 0 to t, let NM be the number of elements of U that belong to exactly I of the sets A,- and d of the sets 8,. That is Paw;=3:E:|[F]/Lljlf]145rl{allzirlrallid, 0L4) i6! i¢1 jeJ j¢J where the sum is again over all l-subsets I C [s] and d-subsets J C [t]. Then clearly, by counting the contribution to SM of each elements a: of U that contribute to NW, foruz l, 122d, we have 51.4: 2 (1;)(Z)Nu, (4.5) (Sugs dSvSt The numbers SM and NM are closely related, and this relation is neatly expressed in terms of ordinary generating functions a t = Z Z Shdxlyd, (4.6) (=0 (1:0 and NC” 31)::21‘03133/(4-7) 1:0 (1:0 Then the following Proposition can be obtained from equations (4.5), (4.6) and (4.7). Proposition 4.1 N(:c+1,y+1) =S(a:,y) (4.8) 41 If we set a: = y = —1 in the equation (4.8), we obtain N(0,0) = S(—1,—1). (4.9) This is the number of elements in U that belong to none of the sets A1, - -- ,A, and B1, - -- ,Bt. Now let a: — 1 and y — 1 take the place of x, y respectively in the equation (4.8) and compare coefficients of x'yd. One finds that . . z+' d+' NM: 2: (_1).+,( i‘)( j’)s.+.-,..j. (4.10) 0955-: OSJ'St-d It is important to study the upper and lower bounds for NM. Therefore we consider truncation . . l+ ' d+ ' Z (‘1)'+J( . z) ( . J) Sl+i,d+j OSiSa 2 J . . l-ki ct+—j It v : —1‘+J( , )( , ) ( .)( .)Nuva 09:30} ) i j “21:“, (+2 d+J ’ 03153 03333 92d+j (4.11) where 0 < a S s—1, 0 < B S t-d and the right side has been obtained by substitution of (4.5). Now interchange the order of summation and obtain 2.<1‘>*"(’ 1' i) C’flw = 2N0) (2) 2H(“ ; ’) (" ; d). 051513 Vid 031579 (4 2) .1 It can be seen that: (—1)a+fi(““—‘) (”7‘“), if u 2 1+ 1,1) 2 d+ 1; 2(-1)‘+j(uz'—l)(v;d) =1 (_lflu «3 )) ifu Zz+1,v=d; gags; , ifu=l,v2d+1; 1, if u = [,0 = d. (4.13) 42 . . z+° d+ Z (—:)'+J( iz)( jj)Sl+:d+j= Nl,d OSiSa 051349 (4.14) La u u—l—l 2 M )( ) uZl+l l C! v v—d—l .-ZN,,.,()( >, de-l-l d fl mm C u§.”"v('i1§)()(“"é‘l)("‘2’1)- v>d+1 If a and fl are both even then the quantity (—1)°‘A + (—1)fiB + (—1)°‘+5C is positive, so that gives us an upper bound. For a lower bound, this quantity should be negative. And that depends on the relative sizes of A, B and C, after we choose a and fl. There are 6 possibilities to consider: (DA (s — l — 1)/2 and B > (t — d— 1)/2. Then (—1)°‘A + (—1)‘BB + (—1)°'+BC is negative for the first four cases in the list above. In 43 case (5), replace a by a + 1. Since a > (s — l — 1)/2, we have (u—l—l) (u—l—l) > a a + 1 for all u such that l + 1 S u S s. This reduces the size of A to A’ but maintains the size of B. Hence their order is preserved, i.e., A’ < B. The altered value of (—1)°A + (—1)BB + (—])°‘+fiC is (—1)°+1A’ + (—1)BB + (-1)°'+5+IC’ which is negative. In case (6), replace B by fl + 1, and apply the same argument. Therefore we have the following Theorem: Theorem 4.2 2 (’1'")() 03150! OSjSfi’ (4 15) . . l+z° d+ ' ° S Nl,d _<_ Z (—1)’+‘7( , ) ( . J)Sl+i,d+j1 0$£§2a z 3 05.7525 where (2a —' 112:8 _1)1 (01', 3') is (2a, Zfi — 1), where 201 > (s -— l — 1)/2; (4-16) (2a—1,2fl), where 2fl> (t—d— 1)/2. 4.2 Configurations Here we use an idea of Bollabés [B080] for representing general cubic graphs. Let V = U1zig2nVi be a partition of V into 3-subsets V5, for z' = 1,--- ,2n. Now we define a graph G’ with vertex set V. The edge set of G consists of 312 vertex-disjoint edges. Thus G is a l-factor with vertex set V = V(G) and it is easy to see that the total number of configurations is (6n)! 23“ - (3n)! ' (4.17) 44 Consider any edge up in G. If both vertices u and v belong to the same set V,- of the partition, the edge is called a l-cycle. Otherwise they are contained in two different sets V,- and V}. If there are exactly two such edges between V,- and Vj, we call this a 2-cycle and if there are three, it is a triple. The next lemma shows that although triples are present, their contribution to all of our asymptotic estimates is negligible. Lemma 4.3 Configurations almost surely have no triples. PROOF. The expected number of triples in a configuration is 2n 3, 6(n — 1))! 2(3")(3n)l (2) '23(n-1>(3(n— 1))! (6n)! ' Elementary operations using Stirling’s formula in the factorials show that the expec- tations is 0(1), Therefore for n —+ 00, the probability of a triple in a configuration tends to zero. Triples are also negligible when the number of double edges is restricted. Lemma 4.4 Triples are negligible in configurations with d 2-cycles when d = o(\/r_z). PROOF. Suppose we have 2n vertices and d pairs of vertices, i.e., {1,2}, {3,4}, ,{2d — 1,2d} where d = o(\/n). We want the number of labeled graphs G with n vertex disjoint edges and no edges of the form {i, 73+ 1} for odd i = 1, to 2d — 1. By using inclusion and exclusion with one property, we want to count the number of good l-factors which has no pairs of the form {i, i + 1} for i = 1, to 2d — 1 where i is odd. The total number of these graphs, i.e., 1-factors, is (2n)! 2"n! ' 45 For odd 2' = 1, . -- ,d, let A,- be the set of graphs for which have a {i,i + 1} pair of vertices. Then 5:: = (3:) $12.32;, where 1 S k S d. Then the total number of good 1-factors is (22.2.33 —1>"( )J‘l}; )2). :7?! (1+2) 1)k(k d)(2n)): ) Since d = o(\/n), we have the following asymptotic result of the number of good (4.18) 1-factors. 2 , 1 The number of good 1-factors ~ £2-% (1 — 573V} “(212) (4.19) N2"n! C] Now, for i = 1, - -- ,2n, let A.- be the set of graphs which have a 1-cycle in V,-. Assume the (22 ") pairs of sets V in the partition are ordered from 1 to (22 “). Let B be the set of graphs which have a 2-cycle in the 3"" pair for j = 1, - -- ,(2;). Let c(2n, 1,d) be number of configurations with exactly I l—cycles and d 2-cycles, possibly triples are included. It will be shown later that they are negligible. Let Sm be the number of configurations which have I 1-cycles and d 2-cycles and no triple edges. Then SM can be found by using the definition in equation (4.3): (W3?.-..)3'5—3—"213:m+o<1>>2anfffffi{33.11922 <44» where the term (1 + o( 1)) allows for a negligible number of triples and is justified by Lemma 4. From equation (4.15), we obtain 2 (*Uifi (l :- z) (d -; j)51+i,d+j OSiSa’ 0953' (4 21) . i l c d - ° S 5(2nll,d) S E (-1)'+’( +z)( fJ)Sl+i,d+j: 031520: 2 ‘7 0535216 46 Then on substituting equation (4.20) in (4.21) and simplifying we have 1 6n! —1 i —1 J' (g . d! ' 231$. (3n)! L: (——iT)T(j!_)] (1 + 0(1)) Siga’ OSjSB' . 1 (6n)! (—1)‘(-1)j < < . __ 1 - c(zn’l’d) - z! . d! 23.. . (3n)! Lag... 41.31 (1 + °( ”’ Difsza (4.22) where both I, and d = o(\/n). Therefore we have: Theorem 4.5 For n —> 00 and l, d = 0(\/1_l), . _ 6‘2 (6n)! c(2n,l,d) _ (1+ 0(1)) 1! . d! 23" . (312),. (4.23) Corollary 4.6 For almost all configurations the numberl of 1-cycles and the number at of 2-cycles satisfy land d = o(\/n). PROOF. . 6‘2 6n ! 6n ! 1d§m6(2n,l,d) =1d=o:(,/;)(1+ 0(1))“ . d! - 23:. (Bin)! = (1 +o(1))——23n(. (1)3n)! (4.24) :1 Corollary 4.7 For any I, d, l é(2n,l,d) = 0(1) 1 (6”)' (4.25) 11.01! ' 23". (3n)1' PROOF. When I and d are arbitrary, the upper bound in (4.22) no longer holds but instead we have: . 1 (6n)! (—lli(-1)j 1 (2n)1+2d(3n)1 d c 2n, l,d < . —,—,— 6 “d ' ( ) - l! - d! 23" - (3n)! LEE,“ 2! - g! (6n)2(1+2d) vii-s23 (4-26) 1 (6n)! = 0(1)“ . d! ' 23.. - (3n)1’ 47 where 614.24 . (2n)l+2d(3n)l,d : O 1). (6n)2(z+2d) Lower bound can be applied similarly. [:1 Corollary 4.8 Mples are negligible in configurations for c(2n, l, d) with arbitrary l and d. PROOF. The proof is similar to the proof of Lemma 4.3 by using (4.25). 4.3 Asymptotic number of general cubic graphs Let c(2n, l, d) be the number of configurations with exactly I 1-cycles and d 2-cycles and no triples. Since the triple edges are negligible, all asymptotic results for 6 hold for c. Let g(2n, [,d) be the number of labeled cubic general graphs G with exactly I loops, d double edges, and no triples. Then we have following relationship between g(2n, 1,d) and c(2n, l, d) by shrinking the 3-vertex sets V,- of configurations to single vertices for graphs. Proposition 4.9 2 c(2n, l, d) = g(2n, l, d) . 3' - ((3) - 2)d(3!)2"-‘-2d (4.27) Then by substituting equations (4.23) and (4.25) into (4.27), we have the following corollaries. Corollary 4.10 For n —> co and l,d = 05/75), 3‘2 6:: l 2 3t , ((3) , 2)d(3!)2n-l-2d (4.28) e‘2 (6n)! 2'-2d (302a 23n.(3n)! no!“ g(2n,l,d) = (1+ 0(1)) = (1+ 0(1)) 48 It can be shown that for large I, d: Corollary 4.11 1 (6n)! 2’-2d (31)?" 23n-(3n)! ll-d! g(2n, (,d) = (0(1)) (4.29) If we sum up the values of g(2n, l, d) using equation (4.28), we have the asymptotic number of general cubic graphs on 2n vertices: Corollary 4.12 For n —> oo, g(2n) = (1+ 0(1)) (3‘32" . 2352;”. (4.30) PROOF. When I, d = o(\/'rl), by using equation (4.28) it easily can be seen that 2 (6n)! 2 g(2N,l,d) : (1+ 0(1))(3f)2n ' 231: . (370' l,d>o For I, d 75 o(\/r—i), we can have three cases as followings: (1) all l,d 2 if for some ion, (2) all d,l 2 {£3 for some un, (3) all I 2 g: d 2 if for some wn, un. Since 2d RT = 0(1)) where d 2 g, and fl 2‘ T! = 0(1)) where l 2 g. It can be shown that e2 (6n)! Zy(2n,l,d) = 0(1) (392" ° 23fl . (3n)! ' 0(1), where the sum is over I > 0, d 2 if, and, similarly, e2 6n)! 29012.net) = 0(1) (39., - 23,5, (3”), ~00). 49 where l _>_ gfl > 0. Therefore (32 617. l 82 6n ! g(2n) = (1+ 0(1))(3!)2n ' 23,5. (3”)! + 0(“(39% ' 23n(- (2)312)! -o(1). C] Let g1(2n) be the number of connected general cubic graphs of order 2n. Then g(2n) and 91(2n) are related by the following sum: " 2n lo g(2n) = 2: 2k -g.(2k)g(2n - 2k) (4.31) k=2 To show that almost all general cubic graphs are connected i.e., g(2n) ~ g1(2n), we need to show that "—1 2n 1: g1(2k)g(2n — 2k) — = (1). (4.32) E (2k) n g(2n) ° Since k - 91(2k) < n - g(2k), it is enough to show that n-l 2n g(2k)g(2n - 2k) = (1). (4.33) 2 (2k) g(2n) ° By using equation (4.30) and some simple estimates, we find the left side of equa- tion (4.33) is n/2 k k 0“) Z (my? lab» — ml (4'34) This sum can be estimated by ksplitting it into two parts according as k S logn or k > log n. Then we find that for 2 S k 3 log n, the value of the sum is 0(n‘2) and for logn < k S n/ 2 it is 0(n‘1(log n)’l/2). Therefore we have the following theorem. Theorem 4.13 Almost all general cubic graphs are connected. For convenience, let (4.35) Then the equation (4.30) can be written g(2n) ~ F(n) - e2. (4.36) Let gl(2n) be the number of general cubics with at least 1 loop. It follows from equa- tion (4.28) with l = 0 that the number of general cubics with no loops is asymptotic to F(n). Therefore g(2n) ~ gl(2n) + F(n). (4.37) Hence the number of general cubics with at least 1 loop is expressed as follows. Proposition 4.14 gl(2n) ~ F(n)(e2 — 1). (4.38) Note that almost all general cubic graphs are connected. Hence we can say that F(n)(e2 — 1) is the asymptotic number of connected general cubic graphs with at least one loop and F (n) is the asymptotic number of connected general cubic graphs with no 100ps. Now if we show that almost all loopless general cubic graphs are 2-connected, then it can be said that the asymptotic number of general cubic graphs with a(G) = 1 is F(n)(e2 — 1). To do this let G be a connected general cubic graph with 2n vertices and no loops, rooted at a bridge, say uv. Therefore [c(G) = 1. Then let a: and y be the vertices other than 12 which are adjacent to u, and s and t be the vertices other than u that are adjacent to 12. Since no is a bridge, :13, y, s and t are all distinct. Delete the vertices u and v with incident edges from G and add new edges my and st to the graph. Then the graph obtained, say H, is a disconnected general cubic graph with 2n — 2 vertices, no loops, and two root edges my and st. This operations can be reversed, i.e., G can be constructed from H by adding the two vertice u and v on the two root edges my and st. 51 It can be seen from the reversal of this construction that the number of connected general cubic graphs with no loops, rooted at a bridge is bounded above by (3"; 3) (g(2n - 2) — gl(2n — 2))2n(2n - 1) (4.39) The factor g(2n — 2) — gl(2n — 2) counts the number of disconnected general cubics of order 2n — 2. The binomial coefficient is larger than the number of ways to choose two edges my and st in different components. The last factors account for the number of ways to label the vertices u and v of a bridge. Hence (4.39) is also an upper bound for the number of connected general cubic graphs with no loops and at least one bridge. Therefore to show that with high probability this do not exist, it is sufficient to show that (3712-3) (g(2n _ 2) —F?(11E)2n — 2))2n(2n - 1) = 0(1). (4.40) Thus we need 0(n“)(9(2n - 2) - 91(2n - 2)) 9(2n) Now g(2n — 2) and gl(2n — 2) are related by the following equation = 0(1). (4.41) g(2n — 2) = i (27;; 2) Ef—lgl(2k)g(2n — 2k — 2). (4.42) k=2 On dividing both sides by g(2n), we have gl(2n—2)_g(2n—2)_n:2(2n—2) k gl(2k)g(2n-2k—2). (4.43) g(2n) _ g(2n) k=2 2k n—1 g(2n) Since 4 g(2n-2) gl(2n—2) 4 "/2 2n—2 g(2k)g(2n—2k—2) 0‘” )( g(2n) ‘ g(2n) >50“ )2( 2k ) g(2n) ’ (4'44) it is enough to show that right side of this equation is 0(1). Using the formula (4.29), Stirling’s formula, and simple estimates, we find that right side of equation (4.44) is n/2 4 1 1 k " 00‘ l: W (n —1)3/2(n — k —1)3/2 [c(n — k — 1)] ' (4'45) k=2 52 This sum can be estimated by splitting it into two parts according as k S logn or k > log n. Then we find that, for 2 S k 3 log n, the value of the sum is 0(n‘1) and, for logn < k S n/2, it is O((log n)‘1/2). Therefore equation (4.41) is established. And we have the following result. Proposition 4.15 Almost all loopless general cubic graphs are 2-connected. Corollary 4.16 The asymptotic number of general cubic graphs G with K(G) = 1 is F(n)(e2 — 1) (4.46) Corollary 4.17 The asymptotic number of 2-connected general cubic graphs is F(n). In a 3-connected general cubic graph, there are no loops and no double edges. There- fore by letting l = 0 and d = 0 in equation (4.29), we obtain g(2n, 0, 0) ~ F(n) . e”2. (4.47) Note that if a general cubic graph has no loops and no double edges, then it is just a cubic graph. We know that almost all cubic graphs are 3-connected [W79c]. Then by (4.47), the asymptotic number of 3—connected general cubic graphs is F(n) - e-2. (4.48) These results are summarized in the following Table. 53 douooaaoo-m .md ommmfifi Acvnm 1 meOA OZ ... A525 an use "A54 . Havana“ .md coco: 880589N .3“ can; A A40 - SEE A o A e v ofiflflcfi Ono ammofi H< A o u _ :82 oz .mnAOvaAES— a.“ 838826 Buooaaooé .3“ A5» a so Em .. 85an A o n a $288 oz Acnsaosoz $8.7 stew .. .AHAOVaAEax .3“ 3% Ages A“ «oxen .. Assn A o A c 82 28 “£2 .24 8885—8; 323 $083 .3 Ass .. A5» magnum 03:0 38:00 :4 2an 54 Open Problems This thesis covers only a portion of the counting problems still open for r-regular graphs, labeled or unlabeled. Unlabeled cubic graphs were tabulated in [R77] and [RW83]. Unlabeled 2- connected graphs [R70] and 3-connected graphs [Wa82] are counted by the method of cycle index sums. Tables of the numbers are given in those papers. The enumera- tion of unlabeled cubic graphs with given connectedness is still open. Thus the more difficult problem to find an efficient enumeration of unlabeled k-connected, r—regular graphs for r > 3 and k =1,--- ,r also is unsolved. Robinson and Wormald also counted the number of labeled 4-regular graphs [RW80]. But the numbers of labeled 4-regular graphs with given connect- edness are not known. Also an efficient enumeration of labeled k-connected, r—regular graphs for r > 4, and k = 1, - -- ,r has not been found. Balaban [Ba70] first discovered the number of general unlabeled cubic graph up to 10 vertices. But after that nothing is known for general labeled or unlabeled r-regular graphs for r > 3. Another open problem is to enumerate unlabeled cfc graphs and claw-free 4-regular graphs. Wormald [W81] proved almost all r-regular graphs are r-connected, for any fixed r 2 3. An asymptotic estimate of the number of r-regular graphs was found by Bollobas [B080], McKay and Wormald [MW91], [MW90] and Bender and Can- field [BeC78] independently. It was shown by Bollobés [B080] and independently McKay and Wormald [MW84] that for r 2 3 Un,r ~ Ln,r/n!1 where Un,,(respectively L”) is the number of unlabeled (respectively labeled) r-regular graphs on n vertices, r is fixed and rn is even. Therefore the asymptotic 55 behavior of unlabeled r-regular graphs can be obtained when r is fixed and rn is even by combining the results above. Wormald [W79a] found the asymptotic number of general r-regular graphs. The problem of determining the asymptotic behavior for general r-regular graphs with given connectivity is open. 56 BIBLIOGRAPHY 57 BIBLIOGRAPHY [CL96] G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman & Hall, 2-6 Boundary Row, London (1996). [Ba70] A.T.Balaban, Chemical Graphs. VIII. Valence isomerism and general cubic graphs, Revue Roumaine de chimie, 15(1970) 463-486. [BeC78] Bender, EA. and Canfield, E.R., The asymptotic number of labeled graphs with given degree sequences, J. Combin. Theory Ser A 24 (1978) 296-307. [B080] B. Bollabas, A probabilistic proof of an asymptotic formula for the number of labeled regular graphs, Europ. J. Combinatorics, 1 (1980) 311-316. [B080] B. Bollabas, The asymptotic number of unlabelled regular graphs, J. London Math. Soc., 26 (1982) 201-206. [Gr92] Harald Gropp, Enumeration of regular graphs 100 years ago, Discrete Math- ematics, 101 (1992) 73-85. [HPa73] F. Harary and EM. Palmer, Graphical Enumeration, Academic, New York (1973). [M83] B.D. McKay, Applications of a technique for labelled enumeration, Congressus Numerantium, 40 (1983) 207-221. [MW91] Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs with degree o(n1/ 2), Combinatorica, 11 (4) (1991) 369-382. [MW90] Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of high degree, Europ. J. Combinatorics, 11 (4) (1990) 565- 580. [MW84] Brendan D. McKay and Nicholas C. Wormald, Automorphisms of random graphs with specified vertices, Combinatorica, 4 (4) (1984) 325-338. 58 [MPaRROx] B.D. McKay, E.M. Palmer, R.C. Read, & R.W. Robinson, The asymp- totic number of claw-free cubic graphs, to appear. [PaRROx] E.M. Palmer, R.C. Read, & R.W. Robinson, Counting claw-free cubic graphs, to appear. [Pa85] E.M. Palmer, Graphical Evolution, John Wiley & Sons, 1985. [R59] R.C. Read, The enumeration of locally restricted graphs(I), J. London Math. Soc., 34 (1959) 417-436. [R60] R.C. Read, The enumeration of locally restricted graphs(II), J. London Math. Soc., 35 (1960) 344-351. [R70] R.C. Read, Some unusual enumeration problems, Ann. New York Acad. Sci, 175 (1970) 314-326. [RW80] R.C. Read and N .C. Wormald, Number of labeled 4—regular graphs, Journal of Graph Theory, 4 (1980) 203-212. [R77] R.W. Robinson, Counting cubic graphs, Journal of Graph Theory, 1 (1977) 285-286. [R70] R.W. Robinson, Enumeration of non-separable graphs, Journal of Combinato- rial Theory, 9 (1970) 327-356. [RW83] R.W. Robinson and NC. Wormald, Numbers of cubic graphs, Journal of Graph Theory, 7 (1983) 463-467. [Wa82] T.R.S. Walsh, Counting unlabeled three-connected and homeomorphically irreducible two-connected graphs, Journal of Combinatorial Theory, Series B 32 (1982) 12-32. [W79a] N.C. Wormald, Some problems in the enumeration of labelled graphs, Doc- toral Thesis , University of Newcastle, NSW, Australia (1979). [W79b] N.C. Wormald, Enumeration of labelled graphs I : 3-connected graphs, J. London Math.Soc. (2), 19 (1979) 7-12. [W79c] N.C. Wormald, Enumeration of labelled graphs II : Cubic graphs with a given connectivity, J. London Math.Soc. (2), 20 (1979) 1-7. [W79d] N.C. Wormald, The exponential generating function of labelled blocks, Dis- crete Mathematics, 25 (1979) 93-96. 59 [W81] N .C. Wormald, The asymptotic connectivity of labeled regular graphs, Journal of Combinatorial Theory, Series B 31 (1982) 156-167. 60 IIIIIIIIIIIIIIIIIIIII 1][I[1][[r]]]I,I]]]]]]]]I