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,7

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).

Links

Table of n, a(n) for n=0..35.

Wikipedia, k-vertex-connected graph

Example

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

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}]

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.

Sequence in context: A215861 A327366 A327069 * A354794 A355401 A195596

Adjacent sequences: A327331 A327332 A327333 * A327335 A327336 A327337

Keyword

nonn,tabl,more

Author

Gus Wiseman, Sep 01 2019

Extensions

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

Status

approved