A327237 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.

1, 1, 0, 1, 0, 1, 1, 3, 3, 1, 4, 40, 15, 4, 1, 56, 660, 267, 35, 5, 1, 1031, 18756, 11022, 1862, 90, 6, 1

Offset: 0

Author

Gus Wiseman, Sep 03 2019

Keywords

• nonn
• tabl
• more

Comments

We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

Examples

			Triangle begins:
   1
   1   0
   1   0   1
   1   3   3   1
   4  40  15   4   1
  56 660 267  35   5   1
		

Crossrefs

Row sums are A006125.

Column k = 0 is A327199.

The covering case is A327126.

Row sums without the first column are A287689.

Cf. A006125, A001187, A013922, A259862, A322389, A326786, A327070, A327114, A327125, A327127, A327198.

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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],cutConnSys[Union@@#,#]==k&]],{n,0,4},{k,0,n}]

Formula

Column-wise binomial transform of A327126.

Extensions

a(21)-a(27) from Jinyuan Wang, Jun 27 2020