login
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.
17
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.
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.
Sequence in context: A199775 A193740 A111408 * A366595 A327237 A092674
KEYWORD
nonn,tabf,more
AUTHOR
Gus Wiseman, Aug 27 2019
EXTENSIONS
a(20)-a(28) from Robert Price, May 25 2021
STATUS
approved