A327231 Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).

0, 0, 1, 3, 18, 250, 5475, 191541, 11065572, 1104254964, 201167132805, 69828691941415, 47150542741904118, 62354150876493659118, 161919876753750972738791, 827272271567137357352991705, 8331016130913639432634637862600, 165634930763383717802534343776893928

Offset: 0

Author

Gus Wiseman, Sep 01 2019

Keywords

• nonn

Comments

A bridge is an edge whose removal disconnected the graph, while an endpoint is a vertex belonging to only one edge. The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a graph whose edge-set is disconnected or empty.

Examples

			The a(2) = 1 through a(4) = 18 edge-sets:
  {12}  {12}  {12}
        {13}  {13}
        {23}  {14}
              {23}
              {24}
              {34}
              {12,13,24}
              {12,13,34}
              {12,14,23}
              {12,14,34}
              {12,23,34}
              {12,24,34}
              {13,14,23}
              {13,14,24}
              {13,23,24}
              {13,24,34}
              {14,23,24}
              {14,23,34}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50

Crossrefs

Column k = 1 of A327148.

The covering version is A327079.

Connected bridged graphs (spanning edge-connectivity 1) are A327071.

BII-numbers of set-systems with non-spanning edge-connectivity 1 are A327099.

Covering set-systems with non-spanning edge-connectivity 1 are A327129.

Cf. A001187, A052446, A322395, A327072, A327073, A327102.

Programs

Mathematica

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],edgeConnSys[#]==1&]],{n,0,4}]

Formula

Binomial transform of A327079.

Extensions

Terms a(6) and beyond from Andrew Howroyd, Sep 11 2019