A140636 Number of connected graphs on n unlabeled nodes that contain at least two cycles.

0, 0, 0, 2, 13, 93, 809, 11005, 260793, 11715808, 1006698524, 164059824899, 50335907853919, 29003487462805642, 31397381142761123838, 63969560113225175845492, 245871831682084026518599099, 1787331725248899088890197955308, 24636021429399867655322650752269938

Offset: 1

Author

Washington Bomfim, May 20 2008

Keywords

• nonn

Comments

Original name: number of unlabeled complex components with n nodes.

We can find in "The Birth of the Giant Component", p. 2, see the first link:

"As each of the random graphs evolved, the story went, never once was there more than a single 'complex' component; i.e. there never were two or more components present simultaneously that were neither trees nor unicyclic."

So a complex component is a connected graph that is neither a tree nor an unicyclic graph.

Examples

			a(4) = 2. See the two complex components with 4 nodes in the Sloane illustration.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• Svante Janson, Donald E. Knuth, Tomasz Łuczak and Boris Pittel, The Birth of the Giant Component, [DOI], Rand. Struct. Alg. 4 (3) (1993) 233-358
• N. J. A. Sloane, Illustration of initial terms of A001349.

Crossrefs

The labeled version is A140638.

Cf. A001349, A000055, A001429, A005703.

Formula

a(n) = A001349(n) - A005703(n).

a(n) = A001349(n) - A000055(n) - A001429(n).

Extensions

Name changed by Andrew Howroyd, Jan 16 2022