A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

0, 0, 1, 3, 28, 475, 14646, 813813, 82060392, 15251272983, 5312295240010, 3519126783483377, 4487168285715524124, 11116496280631563128723, 53887232400918561791887118, 513757147287101157620965656285, 9668878162669182924093580075565776

Offset

0,4

Comments

A graph is covering if the vertex set is the union of the edge set, so there are no isolated vertices.

Links

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

Gus Wiseman, The a(4) = 28 connected covering graphs with at least one endpoint.

Formula

Inverse binomial transform of A327364.

a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

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}]], Union@@#==Range[n]&&Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]], {n, 0, 5}]

Prog

(PARI) seq(n)={Vec(serlaplace(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k! + O(x*x^n))) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Crossrefs

The non-connected version is A327227.

The non-covering version is A327364.

Graphs with endpoints are A245797.

Connected covering graphs are A001187.

Connected graphs with bridges are A327071.

Cf. A004110, A059166, A006125, A006129, A059166, A100743, A141580, A322395, A327105, A327229, A327230, A327366, A327369, A327377.

Sequence in context: A210854 A060545 A108288 * A327071 A346315 A058804

Adjacent sequences: A327359 A327360 A327361 * A327363 A327364 A327365

Keyword

nonn

Author

Gus Wiseman, Sep 04 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

Status

approved