The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A140637 Number of unlabeled graphs of positive excess with n nodes. 0
 0, 0, 0, 2, 15, 110, 936, 12073, 273972, 12003332, 1018992968, 165091159269, 50502031331411, 29054155657134165 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices." If G has just one complex component with 4 nodes, the "non-complex part" of G can be, a) One forest of order 4. There are 6 forests, so 2*6=12 graphs. b) One triangle and one isolated vertex, or 2*1=2 graphs. c) One unicyclic graph of order 4, so 2*2=4 graphs. LINKS Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel, The Birth of the Giant Component. FORMULA a(n) = A000088(n) - A134964(n). EXAMPLE Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes. Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below: O---O...O---O |\..|...|\./| |.\.|...|.X.| |..\|...|/.\| O---O...O---O If G has one complex component with 5 nodes, the non-complex part of G can be, a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs. b) One triangle, so A140636(5) = 13 graphs. If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs. If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs. Finally if G is connected, we have A140636(8), or 11005 graphs. The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073. CROSSREFS Cf. A000088, A005195, A001429, A134964, A140636. Sequence in context: A154635 A062808 A162773 * A022026 A026113 A052874 Adjacent sequences:  A140634 A140635 A140636 * A140638 A140639 A140640 KEYWORD nonn,uned AUTHOR Washington Bomfim, May 21 2008 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 1 16:22 EDT 2020. Contains 337443 sequences. (Running on oeis4.)