A013922 -id:A013922 - cp's OEIS frontend

A002218 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

0, 1, 1, 3, 10, 56, 468, 7123, 194066, 9743542, 900969091, 153620333545, 48432939150704, 28361824488394169, 30995890806033380784, 63501635429109597504951, 244852079292073376010411280, 1783160594069429925952824734641, 24603887051350945867492816663958981

Offset: 1

N. J. A. Sloane

By definition, a(n) gives the number of graphs with zero cutpoints. - Travis Hoppe, Apr 28 2014
For n > 2, a(n) is also the number of simple biconnected graphs on n nodes. - Eric W. Weisstein, Dec 07 2021
This sequence follows R. W. Robinson's definition of a nonseparable graph which includes K_2 but not the singleton graph K_1. This definition is most suited to graphical enumeration. Other authors sometimes include K_1 as a block or exclude K_2 as not 2-connected. - Andrew Howroyd, Feb 26 2023

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 188.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 [terms 1..26 from R. W. Robinson]
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
R. W. Robinson, Computer print-out of first 26 terms [Annotated scanned copy]
R. W. Robinson, Tables
R. W. Robinson, Tables [Local copy, with permission]
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
Andrés Santos, Density Expansion of the Equation of State, in A Concise Course on the Theory of Classical Liquids, Volume 923 of the series Lecture Notes in Physics, pp 33-96, 2016. DOI:10.1007/978-3-319-29668-5_3. See Reference 40.
Andrew J. Schultz and David A. Kofke, Fifth to eleventh virial coefficients of hard spheres, Phys. Rev. E 90, 023301, 4 August 2014
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv preprint arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
Eric Weisstein's World of Mathematics, Biconnected Graph
Eric Weisstein's World of Mathematics, k-Connected Graph

Column k=0 of A325111 (for n>1).
Column sums of A339070.
Row sums of A339071.
The labeled version is A013922.
Cf. A000088 (graphs), A001349 (connected graphs), A006289, A006290, A004115 (rooted case), A010355 (by edges), A241767.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gc=sLog(g), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
{ my(N=12); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ Andrew Howroyd, Dec 28 2020

More terms from Ronald C. Read. Robinson and Walsh list the first 26 terms.
a(1) changed from 0 to 1 by Eric W. Weisstein, Dec 07 2021
a(1) restored to 0 by Andrew Howroyd, Feb 26 2023

A095983 Number of 2-edge-connected labeled graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016

Offset: 0

Yifei Chen (yifei(AT)mit.edu), Jul 17 2004

nonn

From Falk Hüffner, Jun 28 2018: (Start)
Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).
Labeled version of A007146. (End)
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. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019

Jinyuan Wang, Table of n, a(n) for n = 0..82
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.
Gus Wiseman, The a(4) = 10 labeled graphs with spanning edge-connectivity >= 2.
Gus Wiseman, Non-isomorphic representatives of the a(5) = 253 graphs with spanning edge-connectivity >= 2.

Cf. A053549, A198046.
The unlabeled version is A007146.
Row sums of A327069 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with spanning edge-connectivity 2 are A327146.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Graphs without endpoints are A059167.
Graphs with spanning edge-connectivity 1 are A327071.
Cf. A001187, A002218, A052446, A059166, A100743, A322395, A327079, A327144.

seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
seq[16] (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)
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]]]]]]]]];
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,5}] (* Gus Wiseman, Sep 20 2019 *)

\\ here p is initially A053549, q is A198046 as e.g.f.s.
seq(n)={my(v=vector(n));
my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));
my(q=x*exp(p)); p-=q;
for(k=3, n, my(c=polcoeff(p,k)); v[k]=c*(k-1)!; p-=c*q^k);
concat([0],v)} \\ Andrew Howroyd, Jun 18 2018

seq(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))/x-1), -(n+1))} \\ Andrew Howroyd, Dec 28 2020

a(n) = A001187(n) - A327071(n). - Gus Wiseman, Sep 20 2019

Name corrected and more terms from Pavel Irzhavski, Nov 01 2014
Offset corrected by Falk Hüffner, Jun 17 2018
a(12)-a(16) from Andrew Howroyd, Jun 18 2018

A326786 Cut-connectivity of the set-system with BII-number n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 25 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 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 cut-connectivity of a set-system is the minimum number of vertices that must be removed (together with any resulting empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A326853), this is the same as vertex-connectivity (A327051).

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

Cf. A000120, A013922, A029931, A048793, A070939, A305078, A322388, A322389 (same for MM-numbers), A322390, A326031, A326701, A326749, A326753, A326787 (edge-connectivity), A327051 (vertex-connectivity).

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]]]]]]]]];
vertConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Min@@Length/@Select[Subsets[Union@@bpe/@y],Function[del,Length[csm[DeleteCases[DeleteCases[bpe/@y,Alternatives@@del,{2}],{}]]]!=1]]];
Table[vertConn[bpe[n]],{n,0,100}]

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 3, 11, 60, 502, 7403, 197442, 9804368, 902818087, 153721215608, 48443044675155, 28363687700395422, 30996524108446916915, 63502033750022111383196, 244852545022627009655180986, 1783161611023802810566806448531, 24603891215865809635944516464394339

Offset: 1

N. J. A. Sloane

Also unlabeled simple graphs with spanning edge-connectivity >= 2. 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. - Gus Wiseman, Sep 02 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 (terms 1..22 from R. J. Mathar)
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305, Table III.
Eric Weisstein's World of Mathematics, Bridgeless Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
Gus Wiseman, The a(3) = 1 through a(5) = 11 connected bridgeless graphs.

Cf. A005470 (number of simple graphs).
Cf. A007145 (number of simple connected rooted bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263914 (number of simple bridgeless graphs).
Cf. A263915 (number of simple bridged graphs).
The labeled version is A095983.
Row sums of A263296 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Cf. A000719, A001349, A002494, A261919, A327069, A327071, A327074, A327075, A327077, A327109, A327144, A327146.

\\ Translation of theorem 3.2 in Hanlon and Robinson reference. See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); sSolve( gc + gcr^2/2 - sRaise(gcr,2)/2, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 31 2020

a(n) = A001349(n) - A052446(n). - Gus Wiseman, Sep 02 2019

Reference gives first 22 terms.

A322395 Number of labeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Original entry on oeis.org

1, 1, 1, 4, 26, 548, 22504, 1708336, 241874928, 65285161232, 34305887955616, 35573982726480064, 73308270568902715136, 301210456065963448091072, 2471487759846321319412778624, 40526856087731237340916330352896, 1328570640536613080046570271722309632

Offset: 0

Gus Wiseman, Dec 06 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Graph Bridge
Eric Weisstein's World of Mathematics, Endpoint

Cf. A001187, A006125, A007146, A013922, A054921, A095983, A322338, A322387, A322394.

nmax = 16;
seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n + 1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k - 1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
A095983 = seq[nmax];
a[n_] := If[n<3, 1, n+Sum[Binomial[n, k]*A095983[[k+1]]*k^(n-k), {k, 1, n}]];
a /@ Range[0, nmax] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

a(n) = n + Sum_{k=1..n} binomial(n,k)*A095983(k)*k^(n-k) for n >= 3. - Andrew Howroyd, Dec 07 2018

a(6)-a(16) from Andrew Howroyd, Dec 07 2018

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

A322338 Edge-connectivity of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 3, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 3, 0, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 4, 0, 1, 0, 0, 0, 2

Offset: 1

Gus Wiseman, Dec 04 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

The edge-connectivity of an integer partition is the minimum number of parts that must be removed so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

			2093 is the Heinz number of (9,6,4), corresponding to the multiset partition {{1,1},{1,2},{2,2}}, which can be made disconnected by removing only the part {1,2}, so a(2093) = 1.

Wikipedia, k-edge-connected graph

Cf. A001222, A003963, A013922, A054921, A056239, A095983, A112798, A302242, A304714, A304716, A305078, A305079, A322335, A322336, A322337.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[PrimeOmega[n]-Max@@PrimeOmega/@Select[Divisors[n],Length[csm[primeMS/@primeMS[#]]]!=1&],{n,100}]

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

Original entry on oeis.org

1, 2, 4, 5, 6, 7, 8, 16, 17, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 88, 89, 90, 91, 96, 97, 98, 99

Offset: 1

Gus Wiseman, Aug 25 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 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 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  24: {{3},{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}}

Graphs with spanning edge-connectivity >= 2 are counted by A095983.
BII-numbers for vertex-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Set-systems with spanning edge-connectivity 2 are counted by A327130.
Graphs with spanning edge-connectivity 1 are counted by A327145.
Graphs with spanning edge-connectivity 2 are counted by A327146.
Cf. A013922, A322395, A326749, A327041, A327069, A327071, A327097, A327144, A327145.

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,100],spanEdgeConn[Union@@bpe/@bpe[#],bpe/@bpe[#]]==1&]

A326787 Non-spanning edge-connectivity of the set-system with BII-number n.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 2, 3, 1, 1, 2, 1, 0, 0, 1, 1, 1, 1, 1, 0, 2, 0, 2, 1, 3, 1, 2, 0, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 3, 4, 2

Offset: 0

Gus Wiseman, Jul 25 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 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 graph is the minimum number of edges that must be removed to obtain a graph whose edge-set is disconnected or empty.

			Positions of first appearances of each integer together with the corresponding set-systems:
     0: {}
     1: {{1}}
     5: {{1},{1,2}}
    21: {{1},{1,2},{1,3}}
    85: {{1},{1,2},{1,3},{1,2,3}}
   341: {{1},{1,2},{1,3},{1,4},{1,2,3}}
  1365: {{1},{1,2},{1,3},{1,4},{1,2,3},{1,2,4}}
  5461: {{1},{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,3,4}}

Wikipedia, k-edge-connected graph

Cf. A000120, A013922, A048793, A070939, A095983, A322336, A322338 (same for MM-numbers), A326031, A326749, A326753, A326786 (vertex-connectivity).

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]]]]]]]]];
eConn[sys_]:=Length[sys]-Max@@Length/@Select[Subsets[sys],Length[csm[#]]!=1&];
Table[eConn[bpe/@bpe[n]],{n,0,100}]

A322389 Vertex-connectivity of the integer partition with Heinz number n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 05 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

The vertex-connectivity of an integer partition is the minimum number of primes that must be divided out (and any parts then equal to 1 removed) so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

			The integer partition (6,4,3) with Heinz number 455 does not become disconnected or empty if 2 is divided out giving (3,3), or if 3 is divided out giving (4,2), but it does become disconnected or empty if both 2 and 3 are divided out giving (); so a(455) = 2.
195 is the Heinz number of (6,3,2), corresponding to the multiset partition {{1},{2},{1,2}}. Removing the vertex 1 gives {{2},{2}}, while removing 2 gives {{1},{1}}. These are both connected, so both vertices must be removed to obtain a disconnected or empty multiset partition; hence a(195) = 2.

Wikipedia, k-vertex-connected graph

Cf. A003963, A013922, A056239, A095983, A112798, A302242, A304716, A305078, A305079, A322335, A322336, A322338, A322387, A322388, A322390.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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]]]]]]]]];
vertConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Min@@Length/@Select[Subsets[Union@@primeMS/@y],Function[del,Length[csm[DeleteCases[DeleteCases[primeMS/@y,Alternatives@@del,{2}],{}]]]!=1]]];
Array[vertConn@*primeMS,100]

cp's OEIS Frontend

A002218 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A095983 Number of 2-edge-connected labeled graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A326786 Cut-connectivity of the set-system with BII-number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A322395 Number of labeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

A322338 Edge-connectivity of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author