A327196 -id:A327196 - cp's OEIS frontend

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

Gus Wiseman, Aug 27 2019

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.

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

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.

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}

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.

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

A327145 Number of connected set-systems with n vertices and at least one bridge (spanning edge-connectivity 1).

Original entry on oeis.org

0, 1, 4, 56, 4640

Offset: 0

Gus Wiseman, Aug 27 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty set-system.

The BII-numbers of these set-systems are A327111.
Set systems with non-spanning edge-connectivity 1 are A327196, with covering case A327129.
Set systems with spanning edge-connectivity 2 are A327130.
Cf. A003465, A323818, A327069, A327071, A327099, A327108, A327144.

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]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],spanEdgeConn[Range[n],#]==1&]],{n,0,3}]

A327129 Number of connected set-systems covering n vertices with at least one edge whose removal (along with any non-covered vertices) disconnects the set-system (non-spanning edge-connectivity 1).

Original entry on oeis.org

0, 1, 2, 35, 2804

Offset: 0

Gus Wiseman, Aug 27 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty set-system.

			The a(3) = 35 set-systems:
  {123}  {1}{12}{23}   {1}{2}{12}{13}   {1}{2}{3}{12}{13}
         {1}{13}{23}   {1}{2}{12}{23}   {1}{2}{3}{12}{23}
         {1}{2}{123}   {1}{2}{13}{23}   {1}{2}{3}{13}{23}
         {1}{3}{123}   {1}{2}{3}{123}   {1}{2}{3}{12}{123}
         {2}{12}{13}   {1}{3}{12}{13}   {1}{2}{3}{13}{123}
         {2}{13}{23}   {1}{3}{12}{23}   {1}{2}{3}{23}{123}
         {2}{3}{123}   {1}{3}{13}{23}
         {3}{12}{13}   {2}{3}{12}{13}
         {3}{12}{23}   {2}{3}{12}{23}
         {1}{23}{123}  {2}{3}{13}{23}
         {2}{13}{123}  {1}{2}{13}{123}
         {3}{12}{123}  {1}{2}{23}{123}
                       {1}{3}{12}{123}
                       {1}{3}{23}{123}
                       {2}{3}{12}{123}
                       {2}{3}{13}{123}

The restriction to simple graphs is A327079, with non-covering version A327231.
The version for spanning edge-connectivity is A327145, with BII-numbers A327111.
The BII-numbers of these set-systems are A327099.
The non-covering version is A327196.
Cf. A003465, A006129, A263296, A322395, A323818, A327071, A327149.

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]]]]]]]]];
eConn[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],{1,n}]],Union@@#==Range[n]&&eConn[#]==1&]],{n,0,3}]

Inverse binomial transform of A327196.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327145 Number of connected set-systems with n vertices and at least one bridge (spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A327129 Number of connected set-systems covering n vertices with at least one edge whose removal (along with any non-covered vertices) disconnects the set-system (non-spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula