A327144 -id:A327144 - cp's OEIS frontend

A327146 Number of labeled simple graphs with n vertices and spanning edge-connectivity 2.

0, 0, 0, 1, 9, 227

Offset: 0

Gus Wiseman, Aug 27 2019

The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty graph.

Gus Wiseman, The a(4) = 9 simple graphs with spanning edge-connectivity 2.

Column k = 2 of A327069.
BII-numbers of set-systems with spanning edge-connectivity 2 are A327108.
The generalization to set-systems is A327130.
Cf. A006129, A327070, A327071, A327102, A327109, A327111, A327129, 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],{2}]],spanEdgeConn[Range[n],#]==2&]],{n,0,4}]

A327130 Number of set-systems covering n vertices with spanning edge-connectivity 2.

Original entry on oeis.org

0, 0, 0, 32, 9552

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 a(3) = 32 set-systems:
{12}{13}{23}  {1}{12}{13}{23}  {1}{2}{12}{13}{23}  {1}{2}{3}{12}{13}{23}
{12}{13}{123} {2}{12}{13}{23}  {1}{3}{12}{13}{23}  {1}{2}{3}{12}{13}{123}
{12}{23}{123} {3}{12}{13}{23}  {2}{3}{12}{13}{23}  {1}{2}{3}{12}{23}{123}
{13}{23}{123} {1}{12}{13}{123} {1}{2}{12}{13}{123} {1}{2}{3}{13}{23}{123}
              {1}{12}{23}{123} {1}{2}{12}{23}{123}
              {1}{13}{23}{123} {1}{2}{13}{23}{123}
              {2}{12}{13}{123} {1}{3}{12}{13}{123}
              {2}{12}{23}{123} {1}{3}{12}{23}{123}
              {2}{13}{23}{123} {1}{3}{13}{23}{123}
              {3}{12}{13}{123} {2}{3}{12}{13}{123}
              {3}{12}{23}{123} {2}{3}{12}{23}{123}
              {3}{13}{23}{123} {2}{3}{13}{23}{123}

The BII-numbers of these set-systems are A327108.
Set-systems with spanning edge-connectivity 1 are A327145.
The restriction to simple graphs is A327146.
Cf. A003465, A323818, A327069, A327109, A327111, 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],#]==2&]],{n,0,3}]

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}]

A327077 Triangle read by rows where T(n,k) is the number of unlabeled simple connected graphs with n vertices and k bridges.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 3, 1, 0, 2, 0, 11, 4, 3, 0, 3, 0, 60, 25, 14, 7, 0, 6, 0, 502, 197, 91, 34, 18, 0, 11, 0, 7403, 2454, 826, 267, 100, 44, 0, 23, 0, 197442, 48201, 11383, 2800, 831, 259, 117, 0, 47, 0

Offset: 0

Gus Wiseman, Aug 26 2019

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Unlabeled connected graphs with no bridges are counted by A007146 (unlabeled graphs with spanning edge-connectivity >= 2).

			Triangle begins:
     1
     1    0
     0    1   0
     1    0   1   0
     3    1   0   2   0
    11    4   3   0   3  0
    60   25  14   7   0  6  0
   502  197  91  34  18  0 11  0
  7403 2454 826 267 100 44  0 23 0
  ...

Gus Wiseman, Unlabeled connected graphs with 5 vertices and k bridges.

The labeled version is A327072.
Row sums are A001349.
Row sums without the k = 0 column are A052446.
Column k = 0 is A007146, if we assume A007146(0) = 1.
Column k = 1 is A327074.
Column k = n - 1 is A000055.
Cf. A002494, A327071, A327073, A327108, A327109, A327111, A327130, A327144, A327145, A327146.

a(21)-a(54) from Andrew Howroyd, Aug 28 2019

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

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 3, 12, 15, 10, 1, 40, 180, 297, 180, 60, 10, 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 non-covered vertices) to obtain a disconnected or empty graph.

			Triangle begins:
   1
   {}
   0   1
   0   0   3   1
   3  12  15  10   1
  40 180 297 180  60  10   1

Row sums are A006129.
Column k = 0 is A327070.
Column k = 1 is A327079.
The corresponding triangle for vertex-connectivity is A327126.
The corresponding triangle for spanning edge-connectivity is A327069.
The non-covering version is A327148.
The unlabeled version is A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327097, A327099, A327102, A327125, A327129, 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]]]]]]]]];
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[#]==k&]],{n,0,4},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

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

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

Original entry on oeis.org

1, 1, 1, 4, 1, 14, 4, 1, 83, 59, 23, 2, 1232, 2551, 2792, 887, 107, 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 spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices.

			Triangle begins:
     1
     1    1
     4    1
    14    4    1
    83   59   23    2
  1232 2551 2792  887  107   10    1
Row n = 3 counts the following antichains:
  {}             {{1,2,3}}      {{1,2},{1,3},{2,3}}
  {{1}}          {{1,2},{1,3}}
  {{2}}          {{1,2},{2,3}}
  {{3}}          {{1,3},{2,3}}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1},{2}}
  {{1},{3}}
  {{2},{3}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1},{2},{3}}

Row sums are A014466.
Column k = 0 is A327355.
The unlabeled version is A327438.
Cf. A052446, A327062, A327071, A327103, A327111, A327144, A327351, A327353.

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]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],spanEdgeConn[Range[n],#]==k&]],{n,0,4},{k,0,2^n}]//.{foe___,0}:>{foe}

A327074 Number of unlabeled connected graphs with n vertices and exactly one bridge.

Original entry on oeis.org

0, 0, 1, 0, 1, 4, 25, 197, 2454, 48201, 1604016, 93315450, 9696046452, 1822564897453, 625839625866540, 395787709599238772, 464137745175250610865, 1015091996575508453655611, 4160447945769725861550193834, 32088553211819016484736085677320, 467409605282347770524641700949750858

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Unlabeled graphs with no bridges are counted by A007146 (unlabeled graphs with spanning edge-connectivity >= 2).

Gus Wiseman, The a(5) = 4 unlabeled connected graphs with n vertices and exactly one bridge.

The labeled version is A327073.
Unlabeled graphs with at least one bridge are A052446.
The enumeration of unlabeled connected graphs by number of bridges is A327077.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Cf. A001349, A002494, A007146, A263296, A327075, A327111, A327144, A327145.

A007145 = Cases[Import["https://oeis.org/A007145/b007145.txt", "Table"], {, }][[All, 2]];
f[x_] = A007145 . x^Range[lg = Length[A007145]];
(f[x]^2 + f[x^2])/2 + O[x]^lg // CoefficientList[#, x]& (* Jean-François Alcover, Sep 23 2019 *)

G.f.: (f(x)^2 + f(x^2))/2 where f(x) is the g.f. of A007145. - Andrew Howroyd, Aug 25 2019

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

A327147 Smallest BII-number of a set-system with spanning edge-connectivity n.

Original entry on oeis.org

0, 1, 52, 116, 3952, 8052

Offset: 0

Gus Wiseman, Sep 01 2019

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. 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 set-system that is disconnected or covers fewer vertices.

			The sequence of terms together with their corresponding set-systems begins:
     0: {}
     1: {{1}}
    52: {{1,2},{1,3},{2,3}}
   116: {{1,2},{1,3},{2,3},{1,2,3}}
  3952: {{1,3},{2,3},{1,4},{2,4},{3,4},{1,2,3},{1,2,4}}
  8052: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}}

The same for cut-connectivity is A327234.
The same for non-spanning edge-connectivity is A002450.
The spanning edge-connectivity of the set-system with BII-number n is A327144(n).
Cf. A000120, A048793, A070939, A323818, A326031, A326786, A326787, A327041, A327069, A327076, A327108, A327111, A327130, A327145.

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

Original entry on oeis.org

1, 1, 1, 3, 1, 6, 2, 1, 15, 7, 5, 2, 52, 53, 62, 31, 9, 1, 1

Offset: 0

Gus Wiseman, Sep 11 2019

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

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 set-system that is disconnected or covers fewer vertices.

			Triangle begins:
   1
   1  1
   3  1
   6  2  1
  15  7  5  2
  52 53 62 31  9  1  1
The antichains counted in row n = 4 are the following:
  0             {1234}         {12}{134}{234}     {123}{124}{134}{234}
  {1}           {12}{134}      {123}{124}{134}    {12}{13}{14}{23}{24}{34}
  {12}          {123}{124}     {12}{13}{24}{34}
  {123}         {12}{13}{14}   {12}{13}{14}{234}
  {1}{2}        {12}{13}{24}   {12}{13}{14}{23}{24}
  {1}{23}       {12}{13}{234}
  {12}{13}      {12}{13}{14}{23}
  {1}{234}
  {12}{34}
  {1}{2}{3}
  {1}{2}{34}
  {2}{13}{14}
  {12}{13}{23}
  {1}{2}{3}{4}
  {4}{12}{13}{23}

Row sums are A306505.
Column k = 0 is A327437.
The labeled version is A327352.
Cf. A014466, A052446, A327062, A327071, A327103, A327111, A327144, A327352, A327353.

A327110 BII-numbers of set-systems with spanning edge-connectivity 3.

Original entry on oeis.org

116, 117, 118, 119, 124, 125, 126, 127, 1796, 1797, 1798, 1799, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914, 1915, 1916, 1917, 1918, 1919, 1924, 1925, 1926, 1927, 2032, 2033, 2034, 2035, 2036, 2037, 2038, 2039, 2040, 2041, 2042, 2043, 2044

Offset: 1

Gus Wiseman, Oct 03 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. 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 set-system that is disconnected or covers fewer vertices.

			The sequence of all set-systems with spanning edge-connectivity 3 together with their BII-numbers begins:
   116: {{1,2},{1,3},{2,3},{1,2,3}}
   117: {{1},{1,2},{1,3},{2,3},{1,2,3}}
   118: {{2},{1,2},{1,3},{2,3},{1,2,3}}
   119: {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
   124: {{1,2},{3},{1,3},{2,3},{1,2,3}}
   125: {{1},{1,2},{3},{1,3},{2,3},{1,2,3}}
   126: {{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
   127: {{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
  1796: {{1,2},{1,4},{2,4},{1,2,4}}
  1797: {{1},{1,2},{1,4},{2,4},{1,2,4}}
  1798: {{2},{1,2},{1,4},{2,4},{1,2,4}}
  1799: {{1},{2},{1,2},{1,4},{2,4},{1,2,4}}
  1904: {{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1905: {{1},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1906: {{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1907: {{1},{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1908: {{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1909: {{1},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1910: {{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1911: {{1},{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}

Positions of 3's in A327144.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
BII-numbers for spanning edge-connectivity 1 are A327111.
Cf. A001187, A095983, A322395, A326749, A326753, A326787, A327069, A327071, A327103, A327130, A327146, A327147.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Select[Range[1000],spanEdgeConn[Union@@bpe/@bpe[#],bpe/@bpe[#]]==3&]

cp's OEIS Frontend

A327146 Number of labeled simple graphs with n vertices and spanning edge-connectivity 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A327130 Number of set-systems covering n vertices with spanning edge-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A327077 Triangle read by rows where T(n,k) is the number of unlabeled simple connected graphs with n vertices and k bridges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327074 Number of unlabeled connected graphs with n vertices and exactly one bridge.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327147 Smallest BII-number of a set-system with spanning edge-connectivity n.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs