A006024 -id:A006024 - cp's OEIS frontend

A092430 Number of n-node labeled connected mating graphs, cf. A006024.

1, 1, 25, 438, 18388, 1409674, 206682994, 58152537184, 31715884061624, 33827568738189576, 71066571962396085656, 295645506683051376527648, 2444503529745123474354656720, 40269655263141217619453414445968

Offset: 2

Goran Kilibarda, Vladeta Jovovic, Mar 22 2004

nonn

Number of n-node unlabeled connected mating graphs = number of n-node unlabeled connected graphs without endpoints, n>2; cf. A004108.
The number of graphs of this type with n>=1 nodes and 1<=k<=n components defines the triangle
0;
1,0;
1,0,0;
25,3,0,0;
438,10,0,0,0;
18388,385,15,0,0,0;
1409674,10073,105,0,0,0,0;
206682994,561267,5530,105,0,0,0,0;
58152537184,53672556,197344,1260,0,0,0,0,0;
with row sums A007833. - R. J. Mathar, Apr 29 2019

Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.

Andrew Howroyd, Table of n, a(n) for n = 2..50
Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.

Cf. A006024, A079306, A007833, A004108.

Cf. A059166.

a(n)={n!*polcoef(log(sum(i=0, n, 2^binomial(i, 2)*log(1+x + O(x*x^n))^i/i!)/(1+x)), n)} \\ Andrew Howroyd, Sep 09 2018

From Vladeta Jovovic, Mar 28 2004: (Start)
E.g.f.: log((Sum_{n>=0} 2^binomial(n, 2)*log(1+x)^n/n!)/(1+x)).
a(n) = A079306(n) + (-1)^n*(n-1)!. (End)

A102579 Number of n-node labeled digraphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 3, 36, 2160, 577260, 629332740, 2778611237640, 49231195558057800, 3472536190055702938560, 971496134741368475512176960, 1076456769176854177692230640971520, 4723714896453453856832035698858163891200, 82155195331101404797144020808246647196388279040

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 21 2005

nonn

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

Cf. A006024, A102580 (connected), A102596 (oriented), A102598, A369283.

\\ permcount, edges defined in A369283.
a(n) = {my(s=0); forpart(p=n, s += permcount(p)*(-1)^(n-#p)*edges(p, w->1 + 3^w)); s} \\ Andrew Howroyd, Jan 20 2024

a(n) = Sum_{k>=0} 3^k * A369283(n,k). - Andrew Howroyd, Jan 20 2024

a(0)=1 prepended and a(12) onwards from Andrew Howroyd, Jan 20 2024

A102596 Number of n-node labeled oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 2, 14, 396, 34748, 9281784, 7454765736, 17754713559696, 124916711439302928, 2595833697671445752352, 159598823327470451154007008, 29105164897431888477084463394496, 15784299558159474546700473641953798080, 25515085085573055700779453120708128026732416

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 22 2005

nonn

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

Cf. A006024, A102579 (digraphs), A102597 (connected), A102599, A369283.

\\ permcount, edges defined in A369283.
a(n) = {my(s=0); forpart(p=n, s += permcount(p)*(-1)^(n-#p)*edges(p, w->1 + 2^w)); s} \\ Andrew Howroyd, Jan 20 2024

a(n) = Sum_{k>=0} 2^k * A369283(n,k). - Andrew Howroyd, Jan 20 2024

a(0)=1 prepended and a(13) onwards from Andrew Howroyd, Jan 20 2024

A102580 Number of n-node labeled connected digraphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 3, 27, 2025, 566190, 625831920, 2774192113350, 49208948146347570, 3472093007861482740960, 971461407155771477392032600, 1076446082528185671934674675023160, 4723701978908086606944984284949329285400, 82155133922723780601138029235949809990647219040

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 21 2005

nonn

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

Cf. A006024, A102579 (not necessarily connected), A102597 (oriented), A102598 (unlabeled), A369283.

\\ b(n) is A102579(n); permcount, edges defined in A369283.
b(n) = {my(s=0); forpart(p=n, s += permcount(p)*(-1)^(n-#p)*edges(p, w->1 + 3^w)); s}
seq(n) = {Vec(serlaplace(1 + x + log(sum(k=0, n, b(k)*x^k/k!, O(x*x^n))/(1 + x))))} \\ Andrew Howroyd, Jan 20 2024

E.g.f.: 1 + x + log(B(x)/(1 + x)) where B(x) is the e.g.f. of A102579. - Andrew Howroyd, Jan 20 2024

a(0)=1 prepended and a(12) onwards from Andrew Howroyd, Jan 20 2024

A102597 Number of n-node labeled connected oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 2, 8, 352, 32768, 9072896, 7389698048, 17695056717824, 124756911516516352, 2594584522679818518528, 159570269132472101976145920, 29103249711329178773313159168000, 15783921191009840333055992641622114304, 25514864105378775907711095288995558725779456

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 22 2005

nonn

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

Cf. A006024, A102580 (digraphs), A102596 (not necessarily connected), A102599 (unlabeled), A369283.

\\ b(n) is A102596(n); permcount, edges defined in A369283.
b(n) = {my(s=0); forpart(p=n, s += permcount(p)*(-1)^(n-#p)*edges(p, w->1 + 2^w)); s}
seq(n) = {Vec(serlaplace(1 + x + log(sum(k=0, n, b(k)*x^k/k!, O(x*x^n))/(1 + x))))} \\ Andrew Howroyd, Jan 20 2024

E.g.f.: 1 + x + log(B(x)/(1 + x)) where B(x) is the e.g.f. of A102596. - Andrew Howroyd, Jan 20 2024

a(0)=1 prepended and a(13) onwards from Andrew Howroyd, Jan 20 2024

A102598 Number of n-node unlabeled connected digraphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 2, 7, 102, 5034, 886456

Offset: 1

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 22 2005

A102599 Number of n-node unlabeled connected oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 2, 16, 284, 12717, 1468870

Offset: 1

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 22 2005

A101390 Number of n-vertex unlabeled mating graphs (cf. A006024) without endpoints.

Original entry on oeis.org

1, 0, 1, 2, 7, 41, 347, 5447, 158097, 8456025

Offset: 1

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 14 2005

Cf. A006024, A004108, A004110, A059167.

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

Original entry on oeis.org

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

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

Original entry on oeis.org

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

cp's OEIS Frontend

A092430 Number of n-node labeled connected mating graphs, cf. A006024.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

A102579 Number of n-node labeled digraphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A102596 Number of n-node labeled oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A102580 Number of n-node labeled connected digraphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A102597 Number of n-node labeled connected oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A102598 Number of n-node unlabeled connected digraphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

A102599 Number of n-node unlabeled connected oriented graphs whose underlying graphs are mating graphs, cf. A006024.

Views

Author

Keywords

A101390 Number of n-vertex unlabeled mating graphs (cf. A006024) without endpoints.

Views

Author

Keywords

Crossrefs

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

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

Views

Author

Keywords