A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

0, 0, 1, 0, 12, 200, 7680, 506856, 58934848, 12205506096, 4595039095680, 3210660115278000, 4240401342141499392, 10743530775519296581944, 52808688280248604235191296, 507730995579614277599205009240, 9603347831901155679455061048606720, 358743609478638769812094362544644831968

Offset: 0

Author

Gus Wiseman, Aug 24 2019

Keywords

• nonn

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).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• Gus Wiseman, The a(4) = 12 graphs with exactly one bridge.

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.

Cf. A001187, A006129, A052446, A095983, A327069, A327077, A327108, A327111, A327145, A327146.

Programs

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]]1,{i,Length[#]}],True]==1&]],{n,0,5}]

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

Formula

E.g.f.: (x + Sum_{k>=2} A095983(k)*x^k/(k-1)!)^2/2. - Andrew Howroyd, Aug 25 2019

Extensions

Terms a(6) and beyond from Andrew Howroyd, Aug 25 2019