login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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).

LINKS

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

Gus Wiseman, The a(4) = 12 graphs with exactly one bridge.

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(r=x+O(x^n));

my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x^n))));

my(q=x*exp(p)); p-=q;

for(k=3, n-1, my(c=polcoeff(p, k)); r+=c*x^k; p-=c*q^k);

Vec(serlaplace(r^2/2), -(n+1))} \\ Andrew Howroyd, Aug 25 2019

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.

Sequence in context: A036240 A292056 A277311 * A133242 A141836 A083932

Adjacent sequences:  A327070 A327071 A327072 * A327074 A327075 A327076

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 24 2019

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 15 02:31 EDT 2020. Contains 335762 sequences. (Running on oeis4.)