|
|
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
|
|
|
FORMULA
|
|
|
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
|
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
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|