A327069 -id:A327069 - cp's OEIS frontend

A327126 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.

1, 0, 0, 0, 0, 1, 0, 3, 0, 1, 3, 28, 9, 0, 1, 40, 490, 212, 25, 0, 1, 745, 15336, 9600, 1692, 75, 0, 1

Offset: 0

Gus Wiseman, Aug 25 2019

We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

			Triangle begins:
   1
   0   0
   0   0   1
   0   3   0   1
   3  28   9   0   1
  40 490 212  25   0   1

After the first column, same as A327125.
Column k = 0 is A327070.
Column k = 1 is A327114.
Row sums are A006129.
Different from A327069.
Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.
Row sums without the first two columns are A013922.
Cf. A006125, A259862, A322389, A326786, A327114, A327127, A327198, A327237.

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]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==k&]],{n,0,4},{k,0,n}]

a(21)-a(27) from Robert Price, May 20 2021

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.

Original entry on oeis.org

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

A327097 BII-numbers of set-systems with non-spanning edge-connectivity 2.

Original entry on oeis.org

5, 6, 17, 20, 24, 34, 36, 40, 48, 53, 54, 55, 60, 61, 62, 63, 65, 66, 68, 71, 72, 80, 86, 87, 89, 92, 93, 94, 95, 96, 101, 103, 106, 108, 109, 110, 111, 113, 114, 115, 121, 122, 123, 257, 260, 272, 308, 309, 310, 311, 316, 317, 318, 319, 320, 326, 327, 342

Offset: 1

Gus Wiseman, Aug 20 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 non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any isolated vertices) to result in a disconnected or empty set-system.

			The sequence of all set-systems with non-spanning edge-connectivity 2 together with their BII-numbers begins:
   5: {{1},{1,2}}
   6: {{2},{1,2}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  24: {{3},{1,3}}
  34: {{2},{2,3}}
  36: {{1,2},{2,3}}
  40: {{3},{2,3}}
  48: {{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}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}

Positions of 2's in A326787.
BII-numbers for vertex-connectivity 2 are A327082.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for non-spanning edge-connectivity > 1 are A327102.
BII-numbers for spanning edge-connectivity 2 are A327108.
Cf. A007146, A048793, A052446, A059166, A070939, A095983, A263296, A322335, A322338, A322395, A326031, A327041, A327069, A327111.

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]]]]]]]]];
edgeConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[bpe/@#]]!=1&]];
Select[Range[0,100],edgeConn[bpe[#]]==2&]

A327109 BII-numbers of set-systems with spanning edge-connectivity >= 2.

Original entry on oeis.org

52, 53, 54, 55, 60, 61, 62, 63, 84, 85, 86, 87, 92, 93, 94, 95, 100, 101, 102, 103, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 772, 773, 774, 775, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826

Offset: 1

Gus Wiseman, Aug 23 2019

nonn

Differs from A327108 in having 116, 117, 118, 119, 124, 125, 126, 127, ...
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 disconnected or empty set-system.

			The sequence of all set-systems with spanning edge-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}}
   84: {{1,2},{1,3},{1,2,3}}
   85: {{1},{1,2},{1,3},{1,2,3}}
   86: {{2},{1,2},{1,3},{1,2,3}}
   87: {{1},{2},{1,2},{1,3},{1,2,3}}
   92: {{1,2},{3},{1,3},{1,2,3}}
   93: {{1},{1,2},{3},{1,3},{1,2,3}}
   94: {{2},{1,2},{3},{1,3},{1,2,3}}
   95: {{1},{2},{1,2},{3},{1,3},{1,2,3}}
  100: {{1,2},{2,3},{1,2,3}}
  101: {{1},{1,2},{2,3},{1,2,3}}
  102: {{2},{1,2},{2,3},{1,2,3}}
  103: {{1},{2},{1,2},{2,3},{1,2,3}}

Positions of terms >= 2 in  A327144.
Graphs with spanning edge-connectivity >= 2 are counted by A095983.
Graphs with spanning edge-connectivity 2 are counted by A327146.
Set-systems with spanning edge-connectivity 2 are counted by A327130.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity 1 are A327111.
Cf. A326749, A326753, A326787, A327041, A327069, A327071, A327075.

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

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

Original entry on oeis.org

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

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 1, 4, 5, 10, 8, 5, 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
  1
  1  1
  1  1  1  1
  2  2  3  3  1
  4  5 10  8  5  1  1

Gus Wiseman, Unlabeled graphs with 5 vertices, organized by non-spanning edge-connectivity (isolated vertices not shown).

Row sums are A000088.
Column k = 0 is A327235.
The labeled version is A327148.
The covering version is A327201.
Spanning edge-connectivity is A263296.
Vertex-connectivity is A259862.
Cf. A322338, A322396, A326787, A327069, A327077, A327097, A327099, A327102, A327200, A327231.

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]]]]]]]]];
edgeConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Union[normclut/@Select[Subsets[Subsets[Range[n],{2}]],edgeConnSys[#]==k&]]],{n,0,5},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

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

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.

cp's OEIS Frontend

A327126 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

A327097 BII-numbers of set-systems with non-spanning edge-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327109 BII-numbers of set-systems with spanning edge-connectivity >= 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords