login
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
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.
Sequence in context: A060545 A108288 A327362 * A346315 A058804 A327114
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 24 2019
STATUS
approved