login
A327073
Number of labeled simple connected graphs with n vertices and exactly one bridge.
8
0, 0, 1, 0, 12, 200, 7680, 506856, 58934848, 12205506096, 4595039095680, 3210660115278000, 4240401342141499392, 10743530775519296581944, 52808688280248604235191296, 507730995579614277599205009240, 9603347831901155679455061048606720, 358743609478638769812094362544644831968
OFFSET
0,5
COMMENTS
A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).
FORMULA
E.g.f.: (x + Sum_{k>=2} A095983(k)*x^k/(k-1)!)^2/2. - Andrew Howroyd, Aug 25 2019
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, 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&&Count[Table[Length[Union@@Delete[#, i]]<n||Length[csm[Delete[#, i]]]>1, {i, Length[#]}], True]==1&]], {n, 0, 5}]
PROG
(PARI) \\ See A095983.
seq(n)={my(p=x*deriv(log(sum(k=0, n-1, 2^binomial(k, 2) * x^k / k!) + O(x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))^2/2), -(n+1)) } \\ Andrew Howroyd, Dec 28 2020
CROSSREFS
Column k = 1 of A327072.
The unlabeled version is A327074.
Connected graphs with no bridges are A007146.
Connected graphs whose bridges are all leaves are A322395.
Connected graphs with at least one bridge are A327071.
Sequence in context: A355127 A292056 A277311 * A133242 A141836 A363382
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 24 2019
EXTENSIONS
Terms a(6) and beyond from Andrew Howroyd, Aug 25 2019
STATUS
approved