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

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

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

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.

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]]]]]]]]];
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}]

Formula

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