A327129 -id:A327129 - cp's OEIS frontend

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).

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

A327099 BII-numbers of set-systems with non-spanning edge-connectivity 1.

Original entry on oeis.org

1, 2, 4, 7, 8, 16, 22, 23, 25, 28, 29, 30, 31, 32, 37, 39, 42, 44, 45, 46, 47, 49, 50, 51, 57, 58, 59, 64, 67, 73, 74, 75, 76, 77, 78, 79, 82, 83, 90, 91, 97, 99, 105, 107, 128, 256, 262, 263, 278, 279, 280, 281, 284, 285, 286, 287, 292, 293, 294, 295, 300

Offset: 1

Gus Wiseman, Aug 21 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 non-covered vertices) to result in a disconnected or empty set-system.

			The sequence of all set-systems with non-spanning edge-connectivity 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  25: {{1},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  32: {{2,3}}
  37: {{1},{1,2},{2,3}}
  39: {{1},{2},{1,2},{2,3}}
  42: {{2},{3},{2,3}}
  44: {{1,2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  46: {{2},{1,2},{3},{2,3}}

Positions of 1's in A326787.
Simple graphs with non-spanning edge-connectivity 1 are A327071.
BII-numbers for non-spanning edge-connectivity >= 1 are A326749.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for spanning edge-connectivity 1 are A327111.
BII-numbers for vertex-connectivity 1 are A327114.
Covering set-systems with non-spanning edge-connectivity 1 are counted by A327129.
Cf. A048793, A052446, A070939, A322338, A326031, 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]]]]]]]]];
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[#]]==1&]

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

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

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.

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.

A327231 Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).

Original entry on oeis.org

0, 0, 1, 3, 18, 250, 5475, 191541, 11065572, 1104254964, 201167132805, 69828691941415, 47150542741904118, 62354150876493659118, 161919876753750972738791, 827272271567137357352991705, 8331016130913639432634637862600, 165634930763383717802534343776893928

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

A bridge is an edge whose removal disconnected the graph, while an endpoint is a vertex belonging to only one edge. 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.

			The a(2) = 1 through a(4) = 18 edge-sets:
  {12}  {12}  {12}
        {13}  {13}
        {23}  {14}
              {23}
              {24}
              {34}
              {12,13,24}
              {12,13,34}
              {12,14,23}
              {12,14,34}
              {12,23,34}
              {12,24,34}
              {13,14,23}
              {13,14,24}
              {13,23,24}
              {13,24,34}
              {14,23,24}
              {14,23,34}

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

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

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[Select[Subsets[Subsets[Range[n],{2}]],edgeConnSys[#]==1&]],{n,0,4}]

Binomial transform of A327079.

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

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.

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

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

A327099 BII-numbers of set-systems with non-spanning edge-connectivity 1.

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

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

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

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

A327231 Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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