A259862 -id:A259862 - cp's OEIS frontend

A324088 Number of simple non-isomorphic n-vertex graphs of connectivity 7.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 4, 81, 9813, 7499483, 12138114063

Offset: 1

Jens M. Schmidt, Feb 15 2019

Jens M. Schmidt, Data files in graph6 format

Column k=7 of A259862.

Cf. A259862, A052445.

a(13) added by Brendan McKay, Sep 01 2023

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

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 475, 227, 25, 1, 0, 6064, 14736, 10110, 1782, 75, 1, 0

Offset: 0

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

We consider a graph with one vertex and no edges to be disconnected.

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 475 227  25   1   0

Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(1) = 1.
Column k = 1 is A327071.
Column k = 2 is A327146.
The unlabeled version (except with offset 1) is A263296.
Cf. A001187, A095983, A259862, A322338, A326787, A327070, A327072, A327073.

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

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

A263296 Triangle read by rows: T(n,k) is the number of graphs with n vertices with edge connectivity k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 3, 2, 1, 13, 10, 8, 2, 1, 44, 52, 41, 15, 3, 1, 191, 351, 352, 121, 25, 3, 1, 1229, 3714, 4820, 2159, 378, 41, 4, 1, 13588, 63638, 113256, 68715, 14306, 1095, 65, 4, 1, 288597, 1912203, 4602039, 3952378, 1141575, 104829, 3441, 100, 5, 1

Offset: 1

Christian Stump, Oct 13 2015

This is spanning edge-connectivity. The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. The non-spanning edge-connectivity of a graph (A327236) is the minimum number of edges that must be removed to obtain a graph whose edge-set is disconnected or empty. Compare to vertex-connectivity (A259862). - Gus Wiseman, Sep 03 2019

			Triangle begins:
     1;
     1,    1;
     2,    1,    1;
     5,    3,    2,    1;
    13,   10,    8,    2,   1;
    44,   52,   41,   15,   3,  1;
   191,  351,  352,  121,  25,  3, 1;
  1229, 3714, 4820, 2159, 378, 41, 4, 1;
  ...

Georg Grasegger, Table of n, a(n) for n = 1..78 (rows 1..12)
FindStat - Combinatorial Statistic Finder, The edge connectivity of a graph.
Jens M. Schmidt, Combinatorial Data
Gus Wiseman, Unlabeled graphs with 5 vertices organized by spanning edge-connectivity (isolated vertices not shown).

Row sums give A000088, n >= 1.
Columns k=0..10 are A000719, A052446, A052447, A052448, A241703, A241704, A241705, A324096, A324097, A324098, A324099.
Number of graphs with edge connectivity at least k for k=1..10 are A001349, A007146, A324226, A324227, A324228, A324229, A324230, A324231, A324232, A324233.
The labeled version is A327069.
Cf. A002494, A095983, A259862, A327076, A327108, A327109, A327111, A327144, A327145, A327147, A327236.

a(22)-a(55) added by Andrew Howroyd, Aug 11 2019

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

Original entry on oeis.org

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

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

Original entry on oeis.org

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

A327051 Vertex-connectivity of the set-system with BII-number n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 0

Gus Wiseman, Sep 02 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 empty or duplicate edges) to obtain a non-connected set-system or singleton. Except for cointersecting set-systems (A326853), this is the same as cut-connectivity (A326786).

			Positions of first appearances of each integer, together with the corresponding set-systems, are:
     0: {}
     4: {{1,2}}
    52: {{1,2},{1,3},{2,3}}
  2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}

Wikipedia, k-vertex-connected graph

Cut-connectivity is A326786.
Spanning edge-connectivity is A327144.
Non-spanning edge-connectivity is A326787.
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A000120, A013922, A029931, A048793, A070939, A259862, A322389, A323818, A326031, A327125, A327198, 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]}]]
Table[vertConnSys[Union@@bpe/@bpe[n],bpe/@bpe[n]],{n,0,100}]

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.

A052443 Number of simple unlabeled n-node graphs of connectivity 2.

Original entry on oeis.org

0, 0, 1, 2, 7, 39, 332, 4735, 113176, 4629463, 327695586, 40525166511, 8850388574939, 3453378695335727, 2435485662537561705, 3137225298932374490227, 7448146273273417700880931, 32837456713651735794742705141, 270528237651574516777595556494978, 4186091025846007046878947026003803389

Offset: 1

Eric W. Weisstein

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..23
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph.
Gus Wiseman, The a(5) = 7 graphs with vertex-connectivity 2.

Column k=2 of A259862.
Cf. A000719, A002218, A006290, A052442, A052444, A052445.
The labeled version is A327198.
2-vertex-connected graphs are A013922.
Cf. A322387, A327051, A327101, A327334.

A002218 = Cases[Import["https://oeis.org/A002218/b002218.txt", "Table"], {, }][[All, 2]];
A006290 = Cases[Import["https://oeis.org/A006290/b006290.txt", "Table"], {, }][[All, 2]];
a[1] = 0; a[2] = 0; a[3] = 1;
a[n_] := A002218[[n]] - A006290[[n-3]];
Array[a, 23] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

a(n) = A002218(n) - A006290(n) for n > 2. - Andrew Howroyd, Sep 04 2019

Name clarified and a(8)-a(11) by Jens M. Schmidt, Feb 18 2019
a(2)-a(3) corrected by Andrew Howroyd, Aug 28 2019
a(12)-a(20) from Andrew Howroyd, Sep 04 2019

A327082 BII-numbers of set-systems with cut-connectivity 2.

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 256, 257, 384, 385, 512, 514, 640, 642, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850

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.

We define the cut-connectivity (A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039), this is the same as vertex-connectivity (A327334, A327051).

			The sequence of all set-systems with cut-connectivity 2 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}}
  256: {{1,4}}
  257: {{1},{1,4}}
  384: {{4},{1,4}}
  385: {{1},{4},{1,4}}
  512: {{2,4}}
  514: {{2},{2,4}}
  640: {{4},{2,4}}
  642: {{2},{4},{2,4}}
The first term involving an edge of size 3 is 832: {{1,2,3},{1,4},{2,4}}.

Positions of 2's in A326786.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for spanning edge-connectivity 2 are A327108.
The cut-connectivity 1 version is A327098.
The cut-connectivity > 1 version is A327101.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
Cf. A000120, A002218, A013922, A048793, A259862, A322387, A322388, A326031, A327041, A327114.

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

cp's OEIS Frontend

A324088 Number of simple non-isomorphic n-vertex graphs of connectivity 7.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A263296 Triangle read by rows: T(n,k) is the number of graphs with n vertices with edge connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

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

A327051 Vertex-connectivity of the set-system with BII-number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A052443 Number of simple unlabeled n-node graphs of connectivity 2.