A140637 - OEIS

A140637

Number of unlabeled graphs of positive excess with n nodes.

0, 0, 0, 2, 15, 110, 936, 12073, 273972, 12003332, 1018992968, 165091159269, 50502031331411, 29054155657134165, 31426485969804026075, 64001015704527557101231, 245935864153532932681481794, 1787577725145611700547871854870, 24637809253125004524383007473440146

(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.

Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - Gus Wiseman, Feb 13 2024

LINKS

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

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.

MATHEMATICA

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];

Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 5}] (* Gus Wiseman, Feb 14 2024 *)

CROSSREFS

Cf. A000088, A005195, A001429.

The labeled complement is A133686, covering A367869, connected A129271.

The complement is A134964, connected A005703.

The connected covering case is A140636.

The labeled version is A367867, covering A367868, connected A140638.

Set-systems not of this type are A367902, ranks A367906.

Set-systems of this type are A367903, ranks A367907.

For set-systems we have A368094, complement A368095.

For multiset partitions we have A368097, complement A368098.

Factorizations of this type are A368413, complement A368414.