A327148 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of labeled simple graphs with n vertices and non-spanning edge-connectivity k.

1, 1, 1, 1, 1, 3, 3, 1, 4, 18, 27, 14, 1, 56, 250, 402, 240, 65, 10, 1, 1031, 5475, 11277, 9620, 4282, 921, 146, 15, 1

Offset

0,6

Comments

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any isolated vertices) to obtain a disconnected or empty graph.

Links

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

Formula

T(n,k) = Sum_{m = 0..n} binomial(n,m) A327149(m,k). In words, column k is the binomial transform of column k of A327149.

Example

Triangle begins:
   1
   1
   1   1
   1   3   3   1
   4  18  27  14   1
  56 250 402 240  65  10   1

Mathematica

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]]]]]]]]];
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[#]==k&]], {n, 0, 4}, {k, 0, Binomial[n, 2]}]//.{foe___, 0}:>{foe}

Crossrefs

Row sums are A006125.

Column k = 0 is A327199.

Column k = 1 is A327231.

The corresponding triangle for vertex-connectivity is A327125.

The corresponding triangle for spanning edge-connectivity is A327069.

The covering version is A327149.

The unlabeled version is A327236, with covering version A327201.

Cf. A001187, A263296, A322338, A322395, A326787, A327079, A327097, A327099, A327102, A327126, A327144, A327196, A327200, A327201.

Sequence in context: A199775 A193740 A111408 * A366595 A327237 A092674

Adjacent sequences: A327145 A327146 A327147 * A327149 A327150 A327151

Keyword

nonn,tabf,more

Author

Gus Wiseman, Aug 27 2019

Extensions

a(20)-a(28) from Robert Price, May 25 2021

Status

approved