cp's OEIS Frontend

A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1.

%I A327071 #15 Feb 16 2025 08:33:58
%S A327071 0,0,1,3,28,475,14736,818643,82367552,15278576679,5316021393280,
%T A327071 3519977478407687,4487518206535452672,11116767463976825779115,
%U A327071 53887635281876408097483776,513758302006787897939587736715,9668884580476067306398361085853696
%N A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1.
%C A327071 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).
%C A327071 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.
%H A327071 Jean-François Alcover and Vaclav Kotesovec, <a href="/A327071/b327071.txt">Table of n, a(n) for n = 0..82</a> [using A001187 and b-file from A095983]
%H A327071 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BridgedGraph.html">Bridged Graph</a>
%F A327071 a(1) = 0; a(n > 1) = A001187(n) - A095983(n).
%t A327071 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]]]]]]]]];
%t A327071 spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
%t A327071 Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]==1&]],{n,0,4}]
%Y A327071 Column k = 1 of A327069.
%Y A327071 The unlabeled version is A052446.
%Y A327071 Connected graphs without bridges are A007146.
%Y A327071 The enumeration of labeled connected graphs by number of bridges is A327072.
%Y A327071 Connected graphs with exactly one bridge are A327073.
%Y A327071 Graphs with non-spanning edge-connectivity 1 are A327079.
%Y A327071 BII-numbers of set-systems with spanning edge-connectivity 1 are A327111.
%Y A327071 Covering set-systems with spanning edge-connectivity 1 are A327145.
%Y A327071 Graphs with spanning edge-connectivity 2 are A327146.
%Y A327071 Cf. A001187, A001349, A006125, A059166, A322395, A327071, A327077, A327099, A327144.
%K A327071 nonn
%O A327071 0,4
%A A327071 _Gus Wiseman_, Aug 24 2019