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

 

Logo


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

Table of n, a(n) for n=1..14.

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.

License Agreements, Terms of Use, Privacy Policy. .

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