

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
"noncomplex 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:
OO...OO
\.....\./
.\.....X.
..\.../.\
OO...OO
If G has one complex component with 5 nodes, the noncomplex 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 noncomplex 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 noncomplex 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



