A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1.

0, 0, 1, 3, 28, 475, 14736, 818643, 82367552, 15278576679, 5316021393280, 3519977478407687, 4487518206535452672, 11116767463976825779115, 53887635281876408097483776, 513758302006787897939587736715, 9668884580476067306398361085853696

Offset

0,4

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

The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty graph.

Links

Jean-François Alcover and Vaclav Kotesovec, Table of n, a(n) for n = 0..82 [using A001187 and b-file from A095983]

Eric Weisstein's World of Mathematics, Bridged Graph

Formula

a(1) = 0; a(n > 1) = A001187(n) - A095983(n).

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]]]]]]]]];
spanEdgeConn[vts_, eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds], Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], spanEdgeConn[Range[n], #]==1&]], {n, 0, 4}]

Crossrefs

Column k = 1 of A327069.

The unlabeled version is A052446.

Connected graphs without bridges are A007146.

The enumeration of labeled connected graphs by number of bridges is A327072.

Connected graphs with exactly one bridge are A327073.

Graphs with non-spanning edge-connectivity 1 are A327079.

BII-numbers of set-systems with spanning edge-connectivity 1 are A327111.

Covering set-systems with spanning edge-connectivity 1 are A327145.

Graphs with spanning edge-connectivity 2 are A327146.

Cf. A001187, A001349, A006125, A059166, A322395, A327071, A327077, A327099, A327144.

Sequence in context: A060545 A108288 A327362 * A346315 A058804 A327114

Adjacent sequences: A327068 A327069 A327070 * A327072 A327073 A327074

Keyword

nonn

Author

Gus Wiseman, Aug 24 2019

Status

approved