

A327071


Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edgeconnectivity 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 (2edgeconnected graphs).
The spanning edgeconnectivity 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

JeanFrançois Alcover and Vaclav Kotesovec, Table of n, a(n) for n = 0..82 [using A001187 and bfile 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@@#!=vtsLength[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 nonspanning edgeconnectivity 1 are A327079.
BIInumbers of setsystems with spanning edgeconnectivity 1 are A327111.
Covering setsystems with spanning edgeconnectivity 1 are A327145.
Graphs with spanning edgeconnectivity 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



