A327148 -id:A327148 - cp's OEIS frontend

A327200 Number of labeled graphs with n vertices and non-spanning edge-connectivity >= 2.

0, 0, 0, 4, 42, 718, 26262, 1878422, 256204460, 67525498676, 34969833809892, 35954978661632864, 73737437034063350534, 302166248212488958298674, 2475711390267267917290354410, 40563960064630744031043287569378, 1329219366981359393514586291328267704

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

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

Gus Wiseman, The a(4) = 42 graphs with non-spanning edge-connectivity >= 2.

Row sums of A327148 if the first two columns are removed.
BII-numbers of set-systems with non-spanning edge-connectivity >= 2 are A327102.
Graphs with non-spanning edge-connectivity 1 are A327231.
Cf. A001187, A006129, A095983, A182100, A322395, A326787, A327076, A327079, A327097, A327099, A327236.

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],{2}]],eConn[#]>=2&]],{n,0,5}]

Binomial transform of A322395, if we assume A322395(0) = A322395(1) = A322395(2) = 0.

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}

A327354 Number of disconnected or empty antichains of nonempty subsets of {1..n} (non-spanning edge-connectivity 0).

Original entry on oeis.org

1, 1, 2, 8, 53, 747, 45156, 54804920, 19317457655317

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.

			The a(1) = 1 through a(3) = 8 antichains:
  {}  {}         {}
      {{1},{2}}  {{1},{2}}
                 {{1},{3}}
                 {{2},{3}}
                 {{1},{2,3}}
                 {{2},{1,3}}
                 {{3},{1,2}}
                 {{1},{2},{3}}

Column k = 0 of A327353.
The covering case is A120338.
The unlabeled version is A327426.
The spanning edge-connectivity version is A327352.
Cf. A014466, A326787, A327071, A327148, A327236, A327355, A327357.

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]]]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Length[csm[#]]!=1&]],{n,0,4}]

Equals the binomial transform of the exponential transform of A048143 minus A048143.

A327199 Number of labeled simple graphs with n vertices whose edge-set is not connected.

Original entry on oeis.org

1, 1, 1, 1, 4, 56, 1031, 27189, 1165424, 89723096, 13371146135, 3989665389689, 2388718032951812, 2852540291841718752, 6768426738881535155247, 31870401029679493862010949, 297787425565749788134314214272

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Also graphs with non-spanning edge-connectivity 0.

			The a(4) = 4 edge-sets: {}, {12,34}, {13,24}, {14,23}.

Column k = 0 of A327148.
The covering case is A327070.
The unlabeled version is A327235.
Cf. A001187, A006129, A322395, A326787, A327075, A327076, A327079, A327129, A327200, A327201, A327231, A327236.

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

Binomial transform of A327070.

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}

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 6, 46, 655, 17991, 927416, 89009740, 16020407709, 5468601546685, 3578414666656214, 4529751815161579194, 11175105490563109463875, 54043272967471942825421219, 514566625051705610110588073460, 9677104749727084630538798805505880

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

			The a(4) = 46 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}
  {13}  {12,14}  {12,13,24}  {12,13,14,24}
  {14}  {12,23}  {12,13,34}  {12,13,14,34}
  {23}  {12,24}  {12,14,23}  {12,13,23,24}
  {24}  {13,14}  {12,14,34}  {12,13,23,34}
  {34}  {13,23}  {12,23,24}  {12,14,23,24}
        {13,34}  {12,23,34}  {12,14,24,34}
        {14,24}  {12,24,34}  {12,23,24,34}
        {14,34}  {13,14,23}  {13,14,23,34}
        {23,24}  {13,14,24}  {13,14,24,34}
        {23,34}  {13,23,24}  {13,23,24,34}
        {24,34}  {13,23,34}  {14,23,24,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The covering case is A327362.
Graphs with endpoints are A245797.
Graphs with connected edge-set are A287689.
Connected graphs with bridges are A327071.
Covering graphs with endpoints are A327227.
Cf. A001187, A059167, A141580, A322395, A327148, A327335, A327369.

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

seq(n)={my(x=x + O(x*x^n)); Vec(serlaplace(exp(x)*(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!)) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x))^k/k!)))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Binomial transform of A327362.

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

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

A327200 Number of labeled graphs with n vertices and non-spanning edge-connectivity >= 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

A327354 Number of disconnected or empty antichains of nonempty subsets of {1..n} (non-spanning edge-connectivity 0).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327199 Number of labeled simple graphs with n vertices whose edge-set is not connected.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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