A342556 -id:A342556 - cp's OEIS frontend

A004108 Number of n-node unlabeled connected graphs without endpoints.

1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996

Offset: 0

N. J. A. Sloane

nonn

Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004

F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
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 = 0..50 (terms 1..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Gabe Cunningham and Igor Minevich, Graph Products of Groups, arXiv:2502.05648 [math.GR], 2025. See p. 5.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.
R. W. Robinson, Connected graphs without endpoints - computer printout.
Eric Weisstein's World of Mathematics, Connected Graph.

Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).
Cf. A006024, A092430 (n-node labeled connected mating graphs).
See also A261919.
Cf. A342556, A342557.
Counts include those for distance-critical graphs, A349402.

terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}];
A004110 = Table[b[n], {n, 1, terms-1}];
Join[{1}, EULERi[A004110]] (* Jean-François Alcover, Jan 21 2019, after Andrew Howroyd *)

Inverse Euler transform of A004110. - Andrew Howroyd, Sep 09 2018

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

A342557 T(n,m) is the number of unlabeled connected graphs without endpoints on m nodes with n edges, where T(n,m), m <= n, is a triangle read by rows.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 3, 5, 1, 0, 0, 0, 0, 2, 11, 8, 1, 0, 0, 0, 0, 1, 15, 31, 12, 1, 0, 0, 0, 0, 1, 12, 63, 71, 16, 1, 0, 0, 0, 0, 0, 8, 89, 231, 144, 21, 1, 0, 0, 0, 0, 0, 5, 97, 513, 707, 274, 27, 1

Offset: 1

Hugo Pfoertner, May 21 2021

The number of nonzero terms in the n-th row is A083920(n-1). - Hugo Pfoertner, Feb 01 2024

			The triangle begins
  0;
  0, 0;
  0, 0, 1;
  0, 0, 0, 1;
  0, 0, 0, 1, 1;
  0, 0, 0, 1, 3,  1;
  0, 0, 0, 0, 3,  5,  1;
  0, 0, 0, 0, 2, 11,  8,  1;
  0, 0, 0, 0, 1, 15, 31, 12,  1;
  0, 0, 0, 0, 1, 12, 63, 71, 16, 1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50; first 24 rows from Hugo Pfoertner)

Cf. A004108 (column sums), A342556 (row sums).

Cf. A083920, A369932 (not necessarily connected).

\\ Needs G() defined in A369932.
InvEulerMTS(p)={my(n=serprec(p, x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i)}
T(n)={my(r=Vec(InvEulerMTS(substvec(G(n),[x,y],[y,x])))); vector(#r-1, i, Vecrev(Pol(r[i+1]/y),i)) }
{ my(A=T(12)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Feb 07 2024

Bivariate inverse Euler transform of A369932. - Andrew Howroyd, Feb 07 2024

A342558 a(n) is the maximum number of distinct currents > 0 in a network of n one-ohm resistors with a total resistance of 1 ohm.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68

Offset: 1

Hugo Pfoertner and Rainer Rosenthal, May 26 2021

nonn

The resistor networks considered here correspond to multigraphs in which each edge is replaced by one or more one-ohm resistors, and in which there are two distinguished nodes, called poles, between which there is a total resistance of 1 ohm.
It was known that the smallest resistor network with all currents being distinct consists of 21 resistors, found by Duijvestin in 1978. This assumes that the network is planar and thus the analogy to the perfectly tiled squares exists, see A014530. For history and references see link to Stuart Anderson's website "SPSS, Order 21".
In 1983, A. Augusteijn and A. J. W. Duijvestijn  described networks in which the number of resistors in a network with distinct resistances was reduced to 20 by allowing the tiled square to be wrapped onto a cylinder. (see links to their publication and to Stuart Anderson's website "Simple Perfect Square-Cylinders")
For values of n greater than 21 increasingly numerous square divisions with a(n) = n exist so that a(n) = n holds for all n > 21 (see A006983).
In the present sequence, networks based on non-planar graphs are allowed, which makes it possible to find networks with a(n) = n also for n = 18 and n = 19.
In the range from n = 13 to n = 17, larger numbers of distinct currents are found than are possible with the methods for generating Mrs. Perkins's quilts, which naturally correspond to planar graphs.

			Examples for n <= 21 are given in the Pfoertner links. Visualizations of tilings corresponding to optimal networks for n <= 12 are given in the Mathworld "Mrs. Perkins's Quilt" link.

Stuart Anderson, Simple Perfect Squared Squares (SPSSs), Order 21 to 37 and higher orders.
Stuart Anderson, SPSS, Order 21.
Stuart Anderson, Simple Perfect Square-Cylinders (SPSCs); Order 20.
Stuart Anderson, Mrs Perkins's Quilt.
A. Augusteijn and A. J. W. Duijvestijn, Simple perfect square-cylinders of low order, Journal of Combinatorial Theory, Series B, Volume 35, Issue 3, December 1983, Pages 333-337
A. J. W. Duijvestijn, Simple perfect squared square of lowest order, Journal of Combinatorial Theory, Series B, Volume 25, Issue 2, October 1978, Pages 240-243
Ed Pegg Jr., List of solutions for the Mrs. Perkins's Quilt Square packing problem.
Hugo Pfoertner, Examples of networks of n one-ohm-resistors with total resistance of 1 ohm, maximizing the number of distinct currents through the single resistors, May 2021, Jan-Apr 2023
Hugo Pfoertner, Visualization of the resistor networks with n >= 13 using the Mathematica graph function, Jan-Apr 2023
Rainer Rosenthal, Cascade graphs for examples n <= 21, January 2023
Rainer Rosenthal, Network and semi-quilt visualizing a(18), January 2023
Eric Weisstein's World of Mathematics, Mrs. Perkins's Quilt.

Cf. A002962, A005670, A006983, A014530, A160911, A180414, A181340, A217156, A337517, A338593, A342556, A360030.

a(n) = n for n >= 18.

A369290 Number of unlabeled simple graphs without endpoints with n edges.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 6, 10, 25, 68, 182, 538, 1748, 5935, 21585, 82904, 334037, 1406934, 6167455, 28033776, 131770437, 638956188, 3189940453, 16369201031, 86214798929, 465480395911, 2573390342437, 14553415319929, 84118459655982, 496514424803358, 2990633679878654

Offset: 0

Andrew Howroyd, Jan 30 2024

nonn

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

Row sums of A369932.

Cf. A004110 (n vertices), A307316 (multigraph), A342556 (connected).

\\ See also A369932 for a more efficient program.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
seq(n)={my(s=0); forpart(p=2*n, s+=permcount(p)*prod(i=1, #p, 1-x^p[i])*edges(p, w->1+x^w + O(x*x^n))); Vec(s/(2*n)!)}

Euler transform of A342556.

A307317 Number of unlabeled connected leafless loopless multigraphs with n edges.

Original entry on oeis.org

1, 0, 1, 2, 4, 9, 26, 68, 217, 718, 2553, 9574, 38005, 157306, 679682, 3047699, 14150278, 67844305, 335262807, 1704500229, 8902528600, 47704608478, 261960998230, 1472618327415, 8466681788462, 49743177379613, 298407523833717, 1826531247381194, 11399711132242500, 72500116125222893, 469578870456459042

Offset: 0

Eric M. Metodiev, Apr 02 2019

nonn

Connected multigraphs with no loops and no vertices of degree 1.

The initial terms were computed with Nauty.

			For n=3 the multigraphs (as sets of edges) are {(0,1),(0,1),(0,1)} and {(0,1),(0,2),(1,2)}.

Andrew Howroyd, Table of n, a(n) for n = 0..50
P. T. Komiske, E. M. Metodiev, and J. Thaler, Cutting Multiparticle Correlators Down to Size, arXiv:1911.04491 [hep-ph], 2019-2020.
Brendan McKay and Adolfo Piperno, nauty and Traces.

Cf. A076864, A307316 (not necessarily connected), A342556 (simple graphs).

Inverse Euler transform of A307316.

a(0)=1 prepended and a(17) onwards from Andrew Howroyd, Feb 01 2024

cp's OEIS Frontend

A004108 Number of n-node unlabeled connected graphs without endpoints.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A342557 T(n,m) is the number of unlabeled connected graphs without endpoints on m nodes with n edges, where T(n,m), m <= n, is a triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A342558 a(n) is the maximum number of distinct currents > 0 in a network of n one-ohm resistors with a total resistance of 1 ohm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A369290 Number of unlabeled simple graphs without endpoints with n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A307317 Number of unlabeled connected leafless loopless multigraphs with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions