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

Adjacent sequences:  A327068 A327069 A327070 * A327072 A327073 A327074

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 24 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 14 13:27 EDT 2020. Contains 335729 sequences. (Running on oeis4.)