A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset: 0

Author

Gus Wiseman, Feb 18 2024

Keywords

• nonn

Comments

The case of an empty edge set is excluded.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..100

Crossrefs

The covering case is A057500, which is also the covering case of A370317.

This is the connected case of A367862, covering A367863.

A001187 counts connected graphs, A001349 unlabeled.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A062734 counts connected graphs by edge count.

A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.

A143543 counts simple labeled graphs by number of connected components.

A367867 = graphs contradict strict AoC, connected A140638, covering A367868.

Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

Programs

Mathematica

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]

PARI

\\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Formula

Binomial transform of A057500 (if the null graph is not connected).

a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024