A327108 -id:A327108 - cp's OEIS frontend

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

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

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107

Offset: 1

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

A set-system is 2-cut-connected if any single vertex can be removed (along with any empty edges) without making the set-system disconnected or empty. Except for cointersecting set-systems (A326853), this is the same as 2-vertex-connectivity.

			The sequence of all 2-cut-connected set-systems together with their BII-numbers begins:
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}

Positions of numbers >= 2 in A326786.
2-cut-connected graphs are counted by A013922, if we assume A013922(2) = 0.
2-cut-connected integer partitions are counted by A322387.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
The labeled cut-connectivity triangle is A327125, with unlabeled version A327127.
Cf. A000120, A002218, A048793, A070939, A259862, A322388, A326031, A326749, A327097, A327108.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]>=2&]

If (*) is intersection and (-) is complement, we have A327101 * A326704 = A326751 - A058891, i.e., the intersection of A327101 (this sequence) with A326704 (antichains) is the complement of A058891 (singletons) in A326751 (blobs).

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Original entry on oeis.org

0, 0, 1, 0, 12, 200, 7680, 506856, 58934848, 12205506096, 4595039095680, 3210660115278000, 4240401342141499392, 10743530775519296581944, 52808688280248604235191296, 507730995579614277599205009240, 9603347831901155679455061048606720, 358743609478638769812094362544644831968

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 12 graphs with exactly one bridge.

Column k = 1 of A327072.
The unlabeled version is A327074.
Connected graphs with no bridges are A007146.
Connected graphs whose bridges are all leaves are A322395.
Connected graphs with at least one bridge are A327071.
Cf. A001187, A006129, A052446, A095983, A327069, A327077, A327108, A327111, A327145, A327146.

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&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==1&]],{n,0,5}]

\\ See A095983.
seq(n)={my(p=x*deriv(log(sum(k=0, n-1, 2^binomial(k, 2) * x^k / k!) + O(x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))^2/2), -(n+1)) } \\ Andrew Howroyd, Dec 28 2020

E.g.f.: (x + Sum_{k>=2} A095983(k)*x^k/(k-1)!)^2/2. - 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.

A327374 BII-numbers of set-systems with vertex-connectivity 2.

Original entry on oeis.org

52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116

Offset: 1

Gus Wiseman, Sep 04 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 vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

			The sequence of all set-systems with vertex-connectivity 2 together with their BII-numbers begins:
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  67: {{1},{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}
  72: {{3},{1,2,3}}
  73: {{1},{3},{1,2,3}}
  74: {{2},{3},{1,2,3}}
  75: {{1},{2},{3},{1,2,3}}

Positions of 2's in A327051.
Cut-connectivity 2 is A327082.
Spanning edge-connectivity 2 is A327108.
Non-spanning edge-connectivity 2 is A327097.
Vertex-connectivity 3 is A327376.
Labeled graphs with vertex-connectivity 2 are A327198.
Set-systems with vertex-connectivity 2 are A327375.
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A000120, A013922, A048793, A070939, A259862, A326031, A326749, A327336.

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]]]]]]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Select[Range[0,200],vertConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]==2&]

A327375 Number of set-systems with n vertices and vertex-connectivity 2.

Original entry on oeis.org

0, 0, 0, 72, 4752

Offset: 0

Gus Wiseman, Sep 05 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

BII-numbers for vertex-connectivity 2 are A327374.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
Labeled graphs with vertex-connectivity 2 are A327198.
The vertex-connectivity of the set-system with BII-number n is A327051(n).
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A013922, A259862, A322389, A322390, A323818, A327336.

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]]]]]]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],vertConnSys[Range[n],#]==2&]],{n,0,3}]

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

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

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

A327374 BII-numbers of set-systems with vertex-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327375 Number of set-systems with n vertices and vertex-connectivity 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica