A327126 -id:A327126 - 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

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

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 26, 28, 9, 0, 1, 296, 490, 212, 25, 0, 1, 6064, 15336, 9600, 1692, 75, 0, 1, 230896

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   1
    1   0   1
    4   3   0   1
   26  28   9   0   1
  296 490 212  25   0   1

After the first column, same as A327126.
The unlabeled version is A327127.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = 1.
Column k = 1 is A327114, if we assume A327114(1) = 1.
Row sums without the first column are A001187.
Row sums without the first two columns are A013922.
Different from A327069.
Cf. A259862, A322389, A326786, A327082, A327098, A327100, A327101.

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

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

a(1) and a(2) corrected by 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

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 0, 0, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040

Offset: 0

Gus Wiseman, Aug 25 2019

nonn

The cut-connectivity of a graph is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty graph.

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

Column k = 1 of A327126.
The unlabeled version is A052442, if we assume A052442(2) = 0.
Connected non-separable graphs are A013922.
BII-numbers for cut-connectivity 1 are A327098.
Set-systems with cut-connectivity 1 are counted by A327197.
Labeled simple graphs with vertex-connectivity 1 are A327336.
Cf. A001187, A054592, A259862, A322389, A322390, A326786, A327070, A327100, A327125.

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]]]]]]]]];
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],#]==1&]],{n,0,3}]

seq(n)={my(g=log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))); Vec(serlaplace(g-intformal(1+log(x/serreverse(x*deriv(g))))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A001187(n) - A013922(n), if we assume A001187(1) = 0.

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Original entry on oeis.org

0, 0, 1, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040, 9672967865350359173180572164444160

Offset: 0

Gus Wiseman, Sep 02 2019

nonn

Same as A327114 except a(2) = 1.

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.

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

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

Column k = 1 of A327334.
The unlabeled version is A052442.
Connected non-separable graphs are A013922.
Set-systems with vertex-connectivity 1 are A327128.
Labeled simple graphs with cut-connectivity 1 are A327114.
Cf. A006129, A054592, A322389, A322390, A326786, A327070, A327098, A327100, A327125, A327126.

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],#]==1&]],{n,0,4}]

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

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Original entry on oeis.org

0, 0, 4, 72, 29856

Offset: 0

Gus Wiseman, Aug 24 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			Non-isomorphic representatives of the a(3) = 72 set-systems:
  {{123}}
  {{3}{123}}
  {{23}{123}}
  {{2}{3}{123}}
  {{1}{23}{123}}
  {{3}{23}{123}}
  {{12}{13}{23}}
  {{13}{23}{123}}
  {{1}{2}{3}{123}}
  {{1}{3}{23}{123}}
  {{2}{3}{23}{123}}
  {{3}{12}{13}{23}}
  {{2}{13}{23}{123}}
  {{3}{13}{23}{123}}
  {{12}{13}{23}{123}}
  {{1}{2}{3}{23}{123}}
  {{2}{3}{12}{13}{23}}
  {{1}{2}{13}{23}{123}}
  {{2}{3}{13}{23}{123}}
  {{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}}
  {{1}{2}{3}{13}{23}{123}}
  {{2}{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}{123}}

Covering 2-cut-connected graphs are A013922, if we assume A013922(2) = 1.
Covering 1-cut-connected antichains (clutters) are A048143, if we assume A048143(0) = A048143(1) =0.
Covering 2-cut-connected antichains (blobs) are A275307, if we assume A275307(1) = 0.
Covering set-systems with cut-connectivity 2 are A327113.
2-vertex-connected integer partitions are A322387.
BII-numbers of set-systems with cut-connectivity >= 2 are A327101.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Cf. A002218, A003465, A013922, A259862, A323818, A327082, A327126, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]>=2&]],{n,0,3}]

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 2, 0, 1, 13, 11, 7, 2, 0, 1

Offset: 0

Gus Wiseman, Aug 25 2019

A graph with one vertex and no edges is considered to be connected. Except for complete graphs, this is the same as vertex-connectivity (A259862).

There are two ways to define (vertex) connectivity: the minimum size of a vertex cut, and the minimum of the maximum number of internally disjoint paths between two distinct vertices. For non-complete graphs they coincide, which is tremendously useful. For complete graphs with at least 2 vertices, there are no cuts but the second method still works so it is customary to use it to justify the connectivity of K_n being n-1. - Brendan McKay, Aug 28 2019.

			Triangle begins:
   1
   0  1
   1  0  1
   2  1  0  1
   5  3  2  0  1
  13 11  7  2  0  1

Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.

Row sums are A000088.
Column k = 0 is A000719, if we assume A000719(0) = 1.
Column k = 1 is A052442, if we assume A052442(1) = 1 and A052442(2) = 0.
The labeled version is A327125.
A more standard version (zeros removed) is A259862.
Cf. A052443, A322389, A326786, A327082, A327098, A327100, A327113, A327126, A327128, A327197.

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.

A327113 Number of set-systems covering n vertices with cut-connectivity 2.

Original entry on oeis.org

0, 0, 4, 0, 4752

Offset: 0

Gus Wiseman, Aug 24 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			The a(2) = 4 set-systems:
  {{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

Covering graphs with cut-connectivity >= 2 are A013922, if we assume A013922(2) = 1.
Covering antichains (blobs) with cut-connectivity >= 2 are A275307, if we assume A275307(1) = 0.
2-vertex-connected integer partitions are A322387.
Connected covering set-systems are A323818.
Covering set-systems with cut-connectivity >= 2 are A327112.
The cut-connectivity of the set-system with BII-number n is A326786(n).
BII-numbers of set-systems with cut-connectivity 2 are A327082.
Cf. A002218, A003465, A048143, A259862, A322389, A327101, A327113, A327126, A327128, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]==2&]],{n,0,3}]

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

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

A327125 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and 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

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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