A327148 -id:A327148 - cp's OEIS frontend

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 490, 212, 25, 1, 0, 6064, 15336, 9600, 1692, 75, 1, 0, 230896, 851368, 789792, 210140, 14724, 231, 1, 0

Offset: 0

Gus Wiseman, Sep 01 2019

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton. Except for complete graphs, this is the same as cut-connectivity (A327125).

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 490 212  25   1   0

Wikipedia, k-vertex-connected graph

The unlabeled version is A259862.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = A054592(1) = 1.
Column k = 1 is A327336.
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, if we assume A013922(1) = 0.
Cut-connectivity is A327125.
Spanning edge-connectivity is A327069.
Non-spanning edge-connectivity is A327148.
Cf. A322389, A327051, A327070, A327126, A327127, A327350.

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

a(21)-a(35) from Robert Price, May 14 2021

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

Original entry on oeis.org

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

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

Original entry on oeis.org

5, 6, 17, 20, 21, 24, 34, 36, 38, 40, 48, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 66, 68, 69, 70, 71, 72, 80, 81, 84, 85, 86, 87, 88, 89, 92, 93, 94, 95, 96, 98, 100, 101, 102, 103, 104, 106, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121

Offset: 1

Gus Wiseman, Aug 23 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 has non-spanning 2-edge-connectivity >= 2 if it is connected and any single edge can be removed (along with any non-covered vertices) without making the set-system disconnected or empty. Alternatively, these are connected set-systems whose bridges (edges whose removal disconnects the set-system or leaves isolated vertices) are all endpoints (edges intersecting only one other edge).

			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}}
  21: {{1},{1,2},{1,3}}
  24: {{3},{1,3}}
  34: {{2},{2,3}}
  36: {{1,2},{2,3}}
  38: {{2},{1,2},{2,3}}
  40: {{3},{2,3}}
  48: {{1,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}}
  56: {{3},{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}}

Graphs with spanning edge-connectivity >= 2 are counted by A095983.
Graphs with non-spanning edge-connectivity >= 2 are counted by A322395.
Also positions of terms >=2 in A326787.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Cf. A000120, A048793, A059166, A070939, A263296, A326031, A326749, A327076, A327101, A327102, A327108, A327148.

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

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}

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Original entry on oeis.org

1, 7, 60, 968, 31737, 2069963, 267270032, 68629753640, 35171000942697, 36024807353574279, 73784587576805254652, 302228602363365451957792, 2475873310144021668263093201, 40564787336902311168400640561083, 1329227697997490307154018925966130304

Offset: 2

Eric W. Weisstein, May 29 2017

nonn

Also the number of labeled simple graphs with n vertices whose edge-set is connected. - Gus Wiseman, Sep 11 2019

			From _Gus Wiseman_, Sep 11 2019: (Start)
The a(4) = 60 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}
  {13}  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {14}  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {23}  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {24}  {13,14}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {34}  {13,23}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
        {13,34}  {12,14,34}  {12,14,23,24}
        {14,24}  {12,23,24}  {12,14,23,34}
        {14,34}  {12,23,34}  {12,14,24,34}
        {23,24}  {12,24,34}  {12,23,24,34}
        {23,34}  {13,14,23}  {13,14,23,24}
        {24,34}  {13,14,24}  {13,14,23,34}
                 {13,14,34}  {13,14,24,34}
                 {13,23,24}  {13,23,24,34}
                 {13,23,34}  {14,23,24,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}             {12,13,14,23,24,34}
                 {23,24,34}
(End)

Andrew Howroyd, Table of n, a(n) for n = 2..50
Eric Weisstein's World of Mathematics, Triangular Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

The unlabeled version is A292300.

Cf. A001187, A006125, A327070, A327148, A327199, A327235.

Table[With[{g = GraphData[{"Triangular", n}]}, Total[Boole[ConnectedGraphQ[Subgraph[g, #]] & /@ Subsets[VertexList[g]]]]], {n, 2, 5}] - 1
(* Second program: *)
g[n_] := g[n] = If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k) * (n-k-1)/2)*g[k], {k, 1, n-1}]/n]; a[n_] := Sum[Binomial[n, i]*g[i], {i, 2, n}]; Table[a[n], {n, 2, 16}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

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

a(n) = Sum_{i=2..n} binomial(n,i) * A001187(i). - Andrew Howroyd, Jun 07 2017
E.g.f.: exp(x)*(-x + log(Sum_{k>=0} 2^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Sep 11 2019
a(n) = A006125(n) - A327199(n). - Gus Wiseman, Sep 11 2019

Terms a(9) and beyond from Andrew Howroyd, Jun 07 2017

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

A327355 Number of antichains of nonempty subsets of {1..n} that are either non-connected or non-covering (spanning edge-connectivity 0).

Original entry on oeis.org

1, 1, 4, 14, 83, 1232, 84625, 109147467, 38634257989625

Offset: 0

Gus Wiseman, Sep 10 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 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 a(1) = 1 through a(3) = 14 antichains:
  {}  {}         {}
      {{1}}      {{1}}
      {{2}}      {{2}}
      {{1},{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}}

Column k = 0 of A327352.
The covering case is A120338.
The unlabeled version is A327437.
The non-spanning edge-connectivity version is A327354.
Cf. A014466, A327071, A327148, A327353, A327426.

a(n) = A120338(n) + A014466(n) - A006126(n).

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

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0, 11968, 7680, 3600, 2160, 0, 1296, 0, 1047613, 506856, 190365, 68600, 36015, 0, 16807, 0, 169181040, 58934848, 16353792, 4695040, 1433600, 688128, 0, 262144, 0, 51017714393, 12205506096, 2397804444, 500828832, 121706550, 33067440, 14880348, 0, 4782969, 0

Offset: 0

Gus Wiseman, Aug 24 2019

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

Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.

			Triangle begins:
    1
    1   0
    0   1   0
    1   0   3   0
   10  12   0  16   0
  253 200 150   0 125   0

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.

Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.
Column k = 1 is A327073.
Column k = n - 1 is A000272.
Row sums are A001187.
The unlabeled version is A327077.
Row sums without the first column are A327071.
Cf. A001349, A007146, A052446, A054592, A059166, A322395, A327069, 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]]]]]]]]];
Table[If[n<=1&&k==0,1,Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==k&]]],{n,0,4},{k,0,n}]

\\ p is e.g.f. of A053549.
T(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))), v=Vec(1+serreverse(serreverse(log(x/serreverse(x*exp(p))))/exp(x*y+O(x^n))))); vector(#v, k, max(0,k-2)!*Vecrev(v[k], k)) }
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 28 2020

Terms a(21) and beyond from Andrew Howroyd, Dec 28 2020

cp's OEIS Frontend

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

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

Views

Author

Keywords

Comments

Examples

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

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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