A123551 -id:A123551 - cp's OEIS frontend

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

1, 1, 1, 2, 5, 16, 78, 588, 8047, 205914, 10014882, 912908876, 154636289460, 48597794716736, 28412296651708628, 31024938435794151088, 63533059372622888758054, 244916078509480823407040988, 1783406527599529094009748567708, 24605674623474428415849066062642456

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the number of unlabeled mating graphs with n nodes. A mating graph has no two vertices with identical sets of neighbors. - Tanya Khovanova, Oct 23 2008

F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.
F. Harary and E. Palmer, Graphical Enumeration, (1973), compare formula (8.7.11).
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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 0..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Ira M. Gessel and Ji Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
R. J. Mathar, Illustrations for n=1..5 nodes.
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
R. W. Robinson, Graphs without endpoints - computer printout.
N. J. A. Sloane, Illustration of a(0)-a(5).

Row sums of A123551.
Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A006024 (number of labeled mating graphs with n nodes), A129584 (bi-point-determining graphs).
If isolated nodes are forbidden, see A261919.
Cf. A000088.

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]];
a[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]}]; a[0] = 1;
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 27 2018, after Andrew Howroyd *)

\\ Compare A000088.
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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s} \\ Andrew Howroyd, Sep 09 2018

A369932 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

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, 2, 0, 0, 0, 0, 3, 5, 2, 0, 0, 0, 0, 2, 11, 9, 3, 0, 0, 0, 0, 1, 15, 32, 16, 4, 0, 0, 0, 0, 1, 12, 63, 76, 25, 5, 0, 0, 0, 0, 0, 8, 89, 234, 162, 39, 6, 0, 0, 0, 0, 0, 5, 97, 515, 730, 332, 60, 9

Offset: 1

Andrew Howroyd, Feb 07 2024

			Triangle begins:
  0;
  0, 0;
  0, 0, 1;
  0, 0, 0, 1;
  0, 0, 0, 1, 1;
  0, 0, 0, 1, 3,  2;
  0, 0, 0, 0, 3,  5,  2;
  0, 0, 0, 0, 2, 11,  9,  3;
  0, 0, 0, 0, 1, 15, 32, 16,  4;
  0, 0, 0, 0, 1, 12, 63, 76, 25, 5;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums are A369290.
Column sums are A261919.
Main diagonal is A008483.
Cf. A342557 (connected), A123551 (without endpoints).

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)))}
G(n) = {my(s=O(x*x^n)); sum(k=0, n, forpart(p=k, s+=permcount(p) * edges(p, w->1+y^w+O(y*y^n)) * x^k * prod(i=1, #p, 1-(y*x)^p[i], 1+O(x^(n-k+1))) / k!)); s*(1-x)}
T(n)={my(r=Vec(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])) }

T(n,k) = A123551(k,n) - A123551(k-1,n).

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 6, 1, 1, 0, 0, 10, 15, 42, 90, 100, 45, 10, 1, 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1, 1, 0, 0, 35, 105, 462, 2310, 9495, 32130, 85365, 166341, 231861, 237125, 184380, 111870, 53634, 20307, 5985, 1330, 210, 21, 1

Offset: 0

Andrew Howroyd, Feb 07 2024

			Triangle begins:
[0] 1;
[1] 1;
[2] 1, 0;
[3] 1, 0, 0,  1;
[4] 1, 0, 0,  4,  3,  6,    1;
[5] 1, 0, 0, 10, 15,  42,  90,  100,   45,   10,    1;
[6] 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Row sums are A059167.

Cf. A084546, A123551 (unlabeled), A245796 (with endpoints).

\\ row(n) gives n-th row as vector.
row(n)={my(A=x/exp(x*y + O(x*x^n))); Vecrev(polcoef(serlaplace(exp(y*x^2/2 + O(x*x^n)) * sum(k=0, n, (1 + y)^binomial(k, 2)*A^k/k!)), n), 1 + binomial(n,2))}
{ for(n=0, 6, print(row(n))) }

T(n,k) = A084546(n,k) - A245796(n,k).

E.g.f.: exp(y*x^2/2) * Sum_{k>=0} (1 + y)^binomial(k, 2)*(x/exp(y*x))^k/k!.

A368987 Triangle read by rows: T(n,k) is the number of unlabeled point-determining graphs with n nodes and k edges, n >= 0, 0 <= k <= n*(n - 1)/2.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 2, 1, 0, 1, 0, 0, 1, 1, 3, 3, 4, 2, 1, 0, 1, 0, 0, 0, 1, 3, 6, 11, 14, 13, 12, 9, 5, 2, 1, 0, 1, 0, 0, 0, 1, 1, 5, 15, 31, 50, 77, 89, 94, 83, 61, 37, 24, 11, 5, 2, 1, 0, 1, 0, 0, 0, 0, 1, 3, 11, 35, 89, 197, 371, 603, 861, 1068, 1154, 1098, 926, 679, 445, 257, 134, 65, 30, 11, 5, 2, 1, 0, 1

Offset: 0

Andrew Howroyd, Jan 15 2024

Point-determining graphs are also called mating graphs.

			Triangle begins:
[0] 1;
[1] 1;
[2] 0, 1;
[3] 0, 1, 0, 1;
[4] 0, 0, 1, 2, 1, 0,  1;
[5] 0, 0, 1, 1, 3, 3,  4,  2,  1,  0,  1;
[6] 0, 0, 0, 1, 3, 6, 11, 14, 13, 12,  9,  5,  2,  1,  0,  1;
[7] 0, 0, 0, 1, 1, 5, 15, 31, 50, 77, 89, 94, 83, 61, 37, 24, 11, 5, 2, 1, 0, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..175 (rows 0..10)
Ira M. Gessel and Ji Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.

Row sums are A004110.

Cf. A123551 (same row sums), A369283 (labeled).

cp's OEIS Frontend

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A369932 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A368987 Triangle read by rows: T(n,k) is the number of unlabeled point-determining graphs with n nodes and k edges, n >= 0, 0 <= k <= n*(n - 1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs