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

Author

Gus Wiseman, Sep 04 2019

Keywords

• nonn

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.

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.

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

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

Formula

Inverse binomial transform of A327364.

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

Extensions

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