A327149 -id:A327149 - 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

A327070 Number of non-connected simple labeled graphs covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 3, 40, 745, 21028, 973889, 80133088, 12523299729, 3847333778244, 2341705361100633, 2821794389863015840, 6728707109106848947081, 31769173063866390661714996, 297278309767391164611330317921

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

We consider the empty graph to be neither connected (one component) nor disconnected (more than one component).

			The a(4) = 3 graphs:
  {{1,2},{3,4}}
  {{1,3},{2,4}}
  {{1,4},{2,3}}

Column k = 0 of A327149.
The unlabeled version is A327075.
The non-covering version is A327199.
Cf. A000719, A001187, A001349, A002494, A006125, A006129, A054592, A327070.

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]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]!=1&]],{n,0,5}]

a(n) = A006129(n) - A001187(n), if we assume A001187(0) = 0 and A001187(1) = 0.

Inverse binomial transform of A327199.

A327079 Number of labeled simple connected graphs covering n vertices with at least one bridge that is not an endpoint/leaf (non-spanning edge-connectivity 1).

Original entry on oeis.org

0, 0, 1, 0, 12, 180, 4200, 157920, 9673664, 1011129840, 190600639200, 67674822473280, 46325637863907072, 61746583700640860736, 161051184122415878112640, 824849999242893693424992000, 8317799170120961768715123118080

Offset: 0

Gus Wiseman, Aug 25 2019

nonn

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Graphs with no bridges are counted by A095983 (2-edge-connected graphs).

Also labeled simple connected graphs covering n vertices with non-spanning edge-connectivity 1, where the non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty graph.

Column k = 1 of A327149.
The non-covering version is A327231.
Connected bridged graphs (spanning edge-connectivity 1) are A327071.
BII-numbers of graphs with non-spanning edge-connectivity 1 are A327099.
Covering set-systems with non-spanning edge-connectivity 1 are A327129.
Cf. A001187, A006129, A052446, A059166, A322395, A327072, A327073, A327148.

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

a(n) = A001187(n) - A322395(n) for n > 2. - Andrew Howroyd, Aug 27 2019

Inverse binomial transform of A327231.

Terms a(6) and beyond from Andrew Howroyd, Aug 27 2019

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.

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

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 2, 3, 7, 5, 4, 1, 1

Offset: 0

Gus Wiseman, Sep 03 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a disconnected or empty graph, ignoring isolated vertices.

			Triangle begins:
  1
  {}
  0 1
  0 0 1 1
  1 1 2 2 1
  2 3 7 5 4 1 1

Gus Wiseman, Unlabeled graphs covering 5 vertices, organized by non-spanning edge-connectivity.

Row sums are A002494.
Column k = 0 is A327075.
The labeled version is A327149.
Spanning edge-connectivity is A263296.
The non-covering version is A327236 (partial sums).
Cf. A000088, A322338, A322396, A326787, A327076, A327077, A327079, A327126, A327129, A327148, A327235.

A327353 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of subsets of {1..n} with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 2, 3, 8, 7, 3, 1, 53, 27, 45, 36, 6, 747, 511, 1497, 2085, 1540, 693, 316, 135, 45, 10, 1

Offset: 0

Gus Wiseman, Sep 10 2019

An antichain is a set of sets, none of which is a subset of any other.

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.

			Triangle begins:
    1
    1    1
    2    3
    8    7    3    1
   53   27   45   36    6
  747  511 1497 2085 1540  693  316  135   45   10    1
Row n = 3 counts the following antichains:
  {}             {{1}}      {{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
  {{1},{2}}      {{2}}      {{1,2},{2,3}}
  {{1},{3}}      {{3}}      {{1,3},{2,3}}
  {{2},{3}}      {{1,2}}
  {{1},{2,3}}    {{1,3}}
  {{2},{1,3}}    {{2,3}}
  {{3},{1,2}}    {{1,2,3}}
  {{1},{2},{3}}

Row sums are A014466.
Column k = 0 is A327354.
The covering case is A327357.
The version for spanning edge-connectivity is A327352.
The specialization to simple graphs is A327148, with covering case A327149, unlabeled version A327236, and unlabeled covering case A327201.
Cf. A052446, A307249, A326704, A326787, A327071, A327351, A327355.

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]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],eConn[#]==k&]],{n,0,4},{k,0,2^n}]//.{foe___,0}:>{foe}

A327357 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of sets covering n vertices with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 3, 1, 30, 13, 33, 32, 6, 546, 421, 1302, 1915, 1510, 693, 316, 135, 45, 10, 1

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.

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.

			Triangle begins:
    1
    0    1
    1    1
    4    1    3    1
   30   13   33   32    6
  546  421 1302 1915 1510  693  316  135   45   10    1
Row n = 3 counts the following antichains:
  {{1},{2,3}}    {{1,2,3}}  {{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
  {{2},{1,3}}               {{1,2},{2,3}}
  {{3},{1,2}}               {{1,3},{2,3}}
  {{1},{2},{3}}

Row sums are A307249.
Column k = 0 is A120338.
The non-covering version is A327353.
The version for spanning edge-connectivity is A327352.
The specialization to simple graphs is A327149, with unlabeled version A327201.
Cf. A014466, A293606, A326704, A326787, A327071, A327148, A327236, A327351.

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]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,5},{k,0,2^n}]//.{foe___,0}:>{foe}

A327196 Number of connected set-systems with n vertices and at least one bridge that is not an endpoint (non-spanning edge-connectivity 1).

Original entry on oeis.org

0, 1, 4, 44, 2960

Offset: 0

Gus Wiseman, Aug 31 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.

			Non-isomorphic representatives of the a(3) = 44 set-systems:
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{1},{2},{1,2}}
  {{1},{1,2},{2,3}}
  {{1},{2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1},{2},{1,2},{1,3}}
  {{1},{2},{1,3},{2,3}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3}}
  {{1},{2},{3},{1,2},{1,2,3}}

The covering version is A327129.
The BII-numbers of these set-systems are A327099.
The restriction to simple graphs is A327231.
Set-systems with spanning edge-connectivity 1 are A327145.
Cf. A263296, A322395, A327079, A327111, A327148, A327149, A327200.

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

Binomial transform of A327129.

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

A327070 Number of non-connected simple labeled graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327079 Number of labeled simple connected graphs covering n vertices with at least one bridge that is not an endpoint/leaf (non-spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327353 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of subsets of {1..n} with non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327357 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of sets covering n vertices with non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327196 Number of connected set-systems with n vertices and at least one bridge that is not an endpoint (non-spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula