cp's OEIS Frontend

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

a(n) is the number of simple labeled graphs with n nodes and n edges. - Geoffrey Critzer, Nov 02 2014

These graphs are not necessarily covering, but the covering case is A367863, unlabeled A006649, and the unlabeled version is A001434. - Gus Wiseman, Dec 22 2023

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

a(n) is the number of pseudoforests on n nodes. - Eric W. Weisstein, Jun 11 2012

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

a(n) is the number of pseudotrees on n nodes. - Eric W. Weisstein, Jun 11 2012

Also unlabeled connected graphs covering n vertices with at most n edges. For this definition we have a(1) = 0 and possibly a(0) = 0. - Gus Wiseman, Feb 20 2024

a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - Geoffrey Critzer, Oct 12 2012

Also the number of unlabeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

Number of n x n binary matrices without zero rows and with distinct rows up to permutation of rows, cf. A014070.

Row 0 of square array A136555.

From Gus Wiseman, Dec 19 2023: (Start)

Also the number of n-element sets of nonempty subsets of {1..n}, or set-systems with n vertices and n edges (not necessarily covering). The covering case is A054780. For example, the a(3) = 35 set-systems are:

{1}{2}{3} {1}{2}{12} {1}{2}{123} {1}{12}{123} {12}{13}{123}

{1}{2}{13} {1}{3}{123} {1}{13}{123} {12}{23}{123}

{1}{2}{23} {1}{12}{13} {1}{23}{123} {13}{23}{123}

{1}{3}{12} {1}{12}{23} {2}{12}{123}

{1}{3}{13} {1}{13}{23} {2}{13}{123}

{1}{3}{23} {2}{3}{123} {2}{23}{123}

{2}{3}{12} {2}{12}{13} {3}{12}{123}

{2}{3}{13} {2}{12}{23} {3}{13}{123}

{2}{3}{23} {2}{13}{23} {3}{23}{123}

{3}{12}{13} {12}{13}{23}

{3}{12}{23}

{3}{13}{23}

Of these, only {{1},{2},{1,2}}, {{1},{3},{1,3}}, and {{2},{3},{2,3}} do not cover the vertex set.

(End)

The diagonal n = k+1 is A000055(n). - Jonathan Vos Post, Aug 10 2008