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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1. 27
0, 0, 1, 3, 28, 475, 14736, 818643, 82367552, 15278576679, 5316021393280, 3519977478407687, 4487518206535452672, 11116767463976825779115, 53887635281876408097483776, 513758302006787897939587736715, 9668884580476067306398361085853696 (list; graph; refs; listen; history; text; internal format)



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.


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


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


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


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: A108288 A060545 A327362 * A058804 A327114 A327336

Adjacent sequences:  A327068 A327069 A327070 * A327072 A327073 A327074




Gus Wiseman, Aug 24 2019



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 April 16 15:47 EDT 2021. Contains 343050 sequences. (Running on oeis4.)