A013922 -id:A013922 - cp's OEIS frontend

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

0, 0, 0, 1, 9, 212, 9600, 789792, 114812264, 29547629568, 13644009626400, 11489505388892800, 17918588321874717312, 52482523149603539181312, 292311315623259148521270784, 3129388799344153886272170009600, 64965507855114369076680860799267840

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

Andrew Howroyd, Table of n, a(n) for n = 0..25
Gus Wiseman, The a(4) = 9 simple covering graphs with vertex-connectivity 2.

The unlabeled version is A052443.

Cf. A005644, A013922, A052442, A259862, A326786, A327082, A327101, A327112, A327113, A327126, A327227.

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

a(n) = A013922(n) - A005644(n) for n >= 3. - Andrew Howroyd, Dec 26 2020

Terms a(6) and beyond from Andrew Howroyd, Dec 26 2020

A123534 Triangular array T(n,k) giving number of 2-connected graphs with n labeled nodes and k edges (n >= 3, n <= k <= n(n-1)/2).

Original entry on oeis.org

1, 3, 6, 1, 12, 70, 100, 45, 10, 1, 60, 720, 2445, 3535, 2697, 1335, 455, 105, 15, 1, 360, 7560, 46830, 133581, 216951, 232820, 183540, 111765, 53627, 20307, 5985, 1330, 210, 21, 1, 2520, 84000, 835800, 3940440, 10908688, 20317528

Offset: 3

N. J. A. Sloane, Nov 13 2006

			Triangle begins (n >= 3, k >= n):
  n
  3 | 1;
  4 | 3, 6, 1;
  5 | 12, 70, 100, 45, 10, 1;
  6 | 60, 720, 2445, 3535, 2697, 1335, 455, 105, 15, 1;
  ...

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

Andrew Howroyd, Rows 3 through 20, flattened (first 15 rows from R. W. Robinson)

Row sums give A013922.

Cf. A062734, A123527, A322139.

row[n_] := row[n] = Module[{s}, s = (n-1)!*Log[x/InverseSeries[#, x]& @ (x*D[#, x]& @ Log[Sum[(1+y)^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1) ])]; CoefficientList[Coefficient[s, x, n-1]/y^n, y]];
Table[row[n], {n, 3, 15}] // Flatten (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)

row(n)={Vecrev((n-1)!*polcoef(log(x/serreverse(x*deriv(log(sum(k=0, n, (1 + y)^binomial(k, 2) * x^k / k!) + O(x*x^n))))), n-1)/y^n)}
{ for(n=3, 7, print(row(n))) } \\ Andrew Howroyd, Nov 30 2018

A322117 Number of non-isomorphic blobs (2-connected weak antichains) of multisets of weight n.

Original entry on oeis.org

1, 1, 3, 4, 8, 8, 21, 27, 79, 185, 554

Offset: 0

Gus Wiseman, Nov 26 2018

			Non-isomorphic representatives of the a(1) = 1 through a(6) = 21 blobs:
  (1)  (11)    (111)      (1111)        (11111)          (111111)
       (12)    (122)      (1122)        (11222)          (111222)
       (1)(1)  (123)      (1222)        (12222)          (112222)
               (1)(1)(1)  (1233)        (12233)          (112233)
                          (1234)        (12333)          (122222)
                          (11)(11)      (12344)          (122333)
                          (12)(12)      (12345)          (123333)
                          (1)(1)(1)(1)  (1)(1)(1)(1)(1)  (123344)
                                                         (123444)
                                                         (123455)
                                                         (123456)
                                                         (111)(111)
                                                         (112)(122)
                                                         (122)(122)
                                                         (123)(123)
                                                         (123)(233)
                                                         (134)(234)
                                                         (11)(11)(11)
                                                         (12)(12)(12)
                                                         (12)(13)(23)
                                                         (1)(1)(1)(1)(1)(1)

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A002218, A007718, A013922, A275307, A286520, A293994, A304118, A304887, A319719, A319721, A322110, A322118.

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 2, 5, 27, 216, 2311, 30988, 499919, 9431026, 203743252, 4960335470, 134382267082, 4009794148101, 130668970606412, 4617468180528235, 175867725701333896, 7182126650899080024, 313063334893103361130, 14507460736615554141354, 712192629608088061633746

Offset: 0

Gus Wiseman, Nov 28 2018

nonn

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

Row sums of A322147. The unlabeled version is A191970.

Cf. A000664, A002905, A007718, A013922, A054923, A057500, A191646, A291842 (planar case), A321254, A322114, A322115.

multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[multsubs[Range[n+1],2],{n}],And[Union@@#==Range[Max@@Union@@#],Length[csm[#]]==1]&]],{n,5}]

Connected(v)={my(u=vector(#v)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); u}
seq(n)={Vec(vecsum(Connected(vector(2*n, j, (1 + x + O(x*x^n))^binomial(j+1,2)))))} \\ Andrew Howroyd, Nov 28 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 28 2018

A322388 Heinz numbers of 2-vertex-connected integer partitions.

Original entry on oeis.org

13, 29, 37, 39, 43, 47, 61, 65, 71, 73, 79, 87, 89, 91, 101, 107, 111, 113, 117, 129, 137, 139, 149, 151, 163, 167, 169, 173, 181, 183, 185, 193, 195, 197, 199, 203, 213, 223, 229, 233, 235, 237, 239, 247, 251, 257, 259, 261, 263, 267, 269, 271, 273, 281

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

An integer partition is 2-vertex-connected if the prime factorizations of the parts form a connected hypergraph that is still connected if any single prime number is divided out of all the parts (and any parts then equal to 1 are removed).

			The sequence of all 2-vertex-connected integer partitions begins: (1), (6), (10), (12), (6,2), (14), (15), (18), (6,3), (20), (21), (22), (10,2), (24), (6,4), (26), (28), (12,2), (30), (6,2,2), (14,2), (33), (34), (35), (36), (38), (39), (6,6), (40), (42), (18,2), (12,3), (44), (6,3,2), (45), (46).

Wikipedia, k-vertex-connected graph

Cf. A003963, A013922, A056239, A095983, A112798, A218970, A275307, A304716, A305078, A305079, A322336, A322338, A322387, A322389, 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]]]
Select[Range[100],vertConn[primeMS[#]]>1&]

A370064 Triangle read by rows: T(n,k) is the number of simple connected graphs on n labeled nodes with k articulation vertices, (0 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 3, 0, 0, 10, 16, 12, 0, 0, 238, 250, 180, 60, 0, 0, 11368, 8496, 4560, 1920, 360, 0, 0, 1014888, 540568, 211680, 75600, 21000, 2520, 0, 0, 166537616, 61672192, 17186624, 4663680, 1226400, 241920, 20160, 0, 0, 50680432112, 12608406288, 2416430016, 469336896, 98431200, 20109600, 2963520, 181440, 0, 0

Offset: 0

Andrew Howroyd, Feb 23 2024

			Triangle begins:
        1;
        1,      0;
        1,      0,      0;
        1,      3,      0,     0;
       10,     16,     12,     0,     0;
      238,    250,    180,    60,     0,    0;
    11368,   8496,   4560,  1920,   360,    0, 0;
  1014888, 540568, 211680, 75600, 21000, 2520, 0, 0;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
S. Selkow, The enumeration of labeled graphs by number of cutpoints, Discr. Math. 185 (1998), 183-191.

Columns k=0..3 are A013922(n>1), A013923, A013924, A013925.
Row sums are A001187.
Cf. A001710, A325111 (unlabeled version).

J(p, n)={my(u=Vecrev(p,1+n)); forstep(k=n, 1, -1, u[k] -= k*u[k+1]; u[k]/=n+1-k); u}
G(n)={log(x/serreverse(x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))))}
T(n)={my(v=Vec(serlaplace( 1 + ((y-1)*x + serreverse(x/((1-y) + y*exp(G(n)))))/y ))); vector(#v, n, J(v[n], n-1))}
{ my(A=T(7)); for(i=1, #A, print(A[i])) }

T(n, n-2) = n!/2 = A001710(n) for n >= 2.

A010357 Number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges.

Original entry on oeis.org

1, 1, 2, 3, 6, 14, 32, 90, 279, 942, 3468, 13777, 57747, 254671, 1170565, 5580706, 27487418, 139477796, 727458338, 3893078684, 21346838204, 119787629215, 687200870250

Offset: 1

N. J. A. Sloane

Original name: Multi-edge stars with n edges.

			From _Andrew Howroyd_, Nov 23 2020: (Start)
The a(1) = 1 graph is a single edge (K_2 = P_2).
The a(2) = 1 graph is a double edge.
The a(3) = 2 graphs are a triple edge and the triangle (K_3).
The a(4) = 3 graphs are a quadruple edge, a triangle with one double edge and the square (C_4).
(End)

George A. Baker Jr. and John M. Kincaid, The continuous-spin Ising model, g0:phi4:d field theory, and the renormalization group, J. Statist. Phys. 24 (1981), no. 3, 469-528.
Brendan McKay and Adolfo Piperno, nauty and Traces, programs for computing automorphism groups of graphs and digraphs.
Gus Wiseman, Non-isomorphic representatives of the a(1) = 1 through a(6) = 14 unlabeled 2-connected multigraphs.

Row sums of A339160.
Cf. A050535, A076864, A010355, A010359.
A002218 counts unlabeled 2-connected graphs.
A013922 counts labeled 2-connected graphs.
A322140 is a labeled version.
Cf. A002905, A006444, A007718, A275307, A304887.

Name changed by Andrew Howroyd, Dec 05 2020
a(11)-a(20) added using geng/multig from nauty by Andrew Howroyd, Dec 05 2020
a(21)-a(23) from Sean A. Irvine, Apr 18 2024

A322110 Number of non-isomorphic connected multiset partitions of weight n that cannot be capped by a tree.

Original entry on oeis.org

1, 1, 3, 6, 15, 32, 86, 216, 628, 1836, 5822

Offset: 0

Gus Wiseman, Nov 26 2018

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

The density of a multiset partition is defined to be the sum of numbers of distinct elements in each part, minus the number of parts, minus the total number of distinct elements in the whole partition. A multiset partition is a tree if it has more than one part, is connected, and has density -1. A cap is a certain kind of non-transitive coarsening of a multiset partition. For example, the four caps of {{1,1},{1,2},{2,2}} are {{1,1},{1,2},{2,2}}, {{1,1},{1,2,2}}, {{1,1,2},{2,2}}, {{1,1,2,2}}. - Gus Wiseman, Feb 05 2021

			The multiset partition C = {{1,1},{1,2,3},{2,3,3}} is not a tree but has the cap {{1,1},{1,2,3,3}} which is a tree, so C is not counted under a(8).
Non-isomorphic representatives of the a(1) = 1 through a(5) = 32 multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}        {{1,1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}        {{1,1,2,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,2,2}}        {{1,2,2,2,2}}
                    {{1},{1,1}}    {{1,2,3,3}}        {{1,2,2,3,3}}
                    {{2},{1,2}}    {{1,2,3,4}}        {{1,2,3,3,3}}
                    {{1},{1},{1}}  {{1},{1,1,1}}      {{1,2,3,4,4}}
                                   {{1,1},{1,1}}      {{1,2,3,4,5}}
                                   {{1},{1,2,2}}      {{1},{1,1,1,1}}
                                   {{1,2},{1,2}}      {{1,1},{1,1,1}}
                                   {{2},{1,2,2}}      {{1},{1,2,2,2}}
                                   {{3},{1,2,3}}      {{1,2},{1,2,2}}
                                   {{1},{1},{1,1}}    {{2},{1,1,2,2}}
                                   {{1},{2},{1,2}}    {{2},{1,2,2,2}}
                                   {{2},{2},{1,2}}    {{2},{1,2,3,3}}
                                   {{1},{1},{1},{1}}  {{2,2},{1,2,2}}
                                                      {{2,3},{1,2,3}}
                                                      {{3},{1,2,3,3}}
                                                      {{4},{1,2,3,4}}
                                                      {{1},{1},{1,1,1}}
                                                      {{1},{1,1},{1,1}}
                                                      {{1},{1},{1,2,2}}
                                                      {{1},{2},{1,2,2}}
                                                      {{2},{1,2},{1,2}}
                                                      {{2},{1,2},{2,2}}
                                                      {{2},{2},{1,2,2}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{3},{3},{1,2,3}}
                                                      {{1},{1},{1},{1,1}}
                                                      {{1},{2},{2},{1,2}}
                                                      {{2},{2},{2},{1,2}}
                                                      {{1},{1},{1},{1},{1}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Non-isomorphic tree multiset partitions are counted by A321229.
The weak-antichain case is counted by A322117.
The case without singletons is counted by A322118.
Cf. A002218, A007718, A013922, A030019, A056156, A275307, A304118, A304382, A304887, A305052, A305079, A321194.

Corrected by Gus Wiseman, Jan 27 2021

A322118 Number of non-isomorphic connected multiset partitions of weight n with no singletons that cannot be capped by a tree.

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 29, 55, 155, 386, 1171

Offset: 0

Gus Wiseman, Nov 26 2018

The density of a multiset partition is defined to be the sum of numbers of distinct elements in each part, minus the number of parts, minus the total number of distinct elements in the whole partition. A multiset partition is a tree if it has more than one part, is connected, and has density -1. A cap is a certain kind of non-transitive coarsening of a multiset partition. For example, the four caps of {{1,1},{1,2},{2,2}} are {{1,1},{1,2},{2,2}}, {{1,1},{1,2,2}}, {{1,1,2},{2,2}}, {{1,1,2,2}}. - Gus Wiseman, Feb 05 2021

			The multiset partition C = {{1,1},{1,2,3},{2,3,3}} is not a tree but has the cap {{1,1},{1,2,3,3}} which is a tree, so C is not counted under a(8).
Non-isomorphic representatives of the a(2) = 2 through a(6) = 29 multiset partitions:
  {{1,1}}  {{1,1,1}}  {{1,1,1,1}}    {{1,1,1,1,1}}    {{1,1,1,1,1,1}}
  {{1,2}}  {{1,2,2}}  {{1,1,2,2}}    {{1,1,2,2,2}}    {{1,1,1,2,2,2}}
           {{1,2,3}}  {{1,2,2,2}}    {{1,2,2,2,2}}    {{1,1,2,2,2,2}}
                      {{1,2,3,3}}    {{1,2,2,3,3}}    {{1,1,2,2,3,3}}
                      {{1,2,3,4}}    {{1,2,3,3,3}}    {{1,2,2,2,2,2}}
                      {{1,1},{1,1}}  {{1,2,3,4,4}}    {{1,2,2,3,3,3}}
                      {{1,2},{1,2}}  {{1,2,3,4,5}}    {{1,2,3,3,3,3}}
                                     {{1,1},{1,1,1}}  {{1,2,3,3,4,4}}
                                     {{1,2},{1,2,2}}  {{1,2,3,4,4,4}}
                                     {{2,2},{1,2,2}}  {{1,2,3,4,5,5}}
                                     {{2,3},{1,2,3}}  {{1,2,3,4,5,6}}
                                                      {{1,1},{1,1,1,1}}
                                                      {{1,1,1},{1,1,1}}
                                                      {{1,1,2},{1,2,2}}
                                                      {{1,2},{1,1,2,2}}
                                                      {{1,2},{1,2,2,2}}
                                                      {{1,2},{1,2,3,3}}
                                                      {{1,2,2},{1,2,2}}
                                                      {{1,2,3},{1,2,3}}
                                                      {{1,2,3},{2,3,3}}
                                                      {{1,3,4},{2,3,4}}
                                                      {{2,2},{1,1,2,2}}
                                                      {{2,2},{1,2,2,2}}
                                                      {{2,3},{1,2,3,3}}
                                                      {{3,3},{1,2,3,3}}
                                                      {{3,4},{1,2,3,4}}
                                                      {{1,1},{1,1},{1,1}}
                                                      {{1,2},{1,2},{1,2}}
                                                      {{1,2},{1,3},{2,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Non-isomorphic tree multiset partitions are counted by A321229, or A321231 without singletons.
The version with singletons is A322110.
The weak-antichain case is counted by A322138, or A322117 with singletons.
Cf. A002218, A007718, A013922, A030019, A275307, A293994, A304118, A304382, A304887, A305079, A319719, A319721, A321194.

Definition corrected by Gus Wiseman, Feb 05 2021

A322391 Number of integer partitions of n with edge-connectivity 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 9, 3, 14, 8, 17, 13, 35, 17, 49, 35, 67, 53, 114, 69

Offset: 1

Gus Wiseman, Dec 05 2018

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.

			The a(20) = 8 integer partitions:
  (20),
  (12,3,3,2), (9,6,3,2), (8,6,3,3),
  (6,4,4,3,3),
  (6,4,3,3,2,2), (6,3,3,3,3,2),
  (6,3,3,2,2,2,2).

Wikipedia, k-edge-connected graph

Cf. A007718, A013922, A054921, A095983, A218970, A275307, A304716, A305078, A305079, A322335, A322336, A322387, 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]]]]]]]]];
edgeConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[primeMS/@#]]!=1&]];
Table[Length[Select[IntegerPartitions[n],edgeConn[#]==1&]],{n,20}]

cp's OEIS Frontend

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A123534 Triangular array T(n,k) giving number of 2-connected graphs with n labeled nodes and k edges (n >= 3, n <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A322117 Number of non-isomorphic blobs (2-connected weak antichains) of multisets of weight n.

Views

Author

Keywords

Examples

Links

Crossrefs

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A322388 Heinz numbers of 2-vertex-connected integer partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A370064 Triangle read by rows: T(n,k) is the number of simple connected graphs on n labeled nodes with k articulation vertices, (0 <= k <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A010357 Number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A322110 Number of non-isomorphic connected multiset partitions of weight n that cannot be capped by a tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A322118 Number of non-isomorphic connected multiset partitions of weight n with no singletons that cannot be capped by a tree.

Views