A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 490, 212, 25, 1, 0, 6064, 15336, 9600, 1692, 75, 1, 0, 230896, 851368, 789792, 210140, 14724, 231, 1, 0

Offset: 0

Author

Gus Wiseman, Sep 01 2019

Keywords

• nonn
• tabl
• more

Comments

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton. Except for complete graphs, this is the same as cut-connectivity (A327125).

Examples

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 490 212  25   1   0
		

Links

• Wikipedia, k-vertex-connected graph

Crossrefs

The unlabeled version is A259862.

Row sums are A006125.

Column k = 0 is A054592, if we assume A054592(0) = A054592(1) = 1.

Column k = 1 is A327336.

Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.

Row sums without the first two columns are A013922, if we assume A013922(1) = 0.

Cut-connectivity is A327125.

Spanning edge-connectivity is A327069.

Non-spanning edge-connectivity is A327148.

Cf. A322389, A327051, A327070, A327126, A327127, A327350.

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

Extensions

a(21)-a(35) from Robert Price, May 14 2021