A004110 -id:A004110 - cp's OEIS frontend

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

0, 1, 1, 4, 12, 60, 378, 3843, 64455, 1921532, 104098702, 10348794144, 1893781768084, 639954768875644, 400905675004630820, 467554784370658979194, 1019317687720204607541914, 4170177760438554428852944352, 32130458453030025927403299167172

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Minimum Vertex Degree
Gus Wiseman, The a(2) = 1 through a(5) = 12 unlabeled graphs with minimum degree 1.

Column k = 1 of A294217.
A diagonal of A263293.
The labeled version is A327227.
The generalization to set-systems is A327335, with covering case A327230.
Unlabeled covering graphs are A002494.
Cf. A000088, A004110, A100743, A141580, A245797, A261919, A327105, A327362, A327364, A327366, A327372.

a(n) = A002494(n) - A261919(n).

First differences of A141580. - Andrew Howroyd, Jan 11 2021

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.

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 9, 45, 160, 1018, 6956, 67704, 830392, 13539344, 288643968, 8112651795, 300974046019, 14796399706863, 967194378235406, 84374194347669628, 9856131011755992817, 1546820212559671605395

Offset: 1

Felix Goldberg (felixg(AT)tx.technion.ac.il), Oct 30 2003

nonn

The terms were computed using the program Nauty.

As shown in the Hardt et al. reference, this sequence (for n >= 3) also enumerates the connected point-determining bipartite graphs. - Justin M. Troyka, Nov 27 2013

			Consider n = 4.  There is one connected bipartite graph with minimum degree at least 2: the square graph.  Also there is one connected point-determining bipartite graph: the graph *--*--*--*. - _Justin M. Troyka_, Nov 27 2013

Brendan McKay, Nauty
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO].

Cf. A006024, A004110 (labeled and unlabeled point-determining graphs [the latter is also unlabeled graphs w/ min. degree >= 2]).
Cf. A059167 (labeled graphs w/ min. degree >= 2).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs [the latter is also unlabeled connected graphs w/ min. degree >= 2]).
Cf. A059166 (labeled connected graphs w/ min. degree >= 2).
Cf. A232699, A218090 (labeled and unlabeled point-determining bipartite graphs).
Cf. A232700 (labeled connected point-determining bipartite graphs).

More terms from Andy Hardt, Oct 31 2012

A101388 Number of n-vertex unlabeled digraphs without endpoints.

Original entry on oeis.org

1, 1, 1, 8, 137, 7704, 1413982, 855543836, 1775124241697, 12985137979651848, 340909258684048264585, 32512676857544231506934756, 11365672344040389664750137465767, 14668676509227095069116619104786898732, 70315084528883620836175544247562749711989951

Offset: 0

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

nonn

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

Cf. A100548 (labeled case), A004110, A004108, A059166, A059167, A101389.

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, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
seq(n)=Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^3 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2)) \\ Andrew Howroyd, Jan 22 2021

a(0)=1 prepended and terms a(7) and beyond from Andrew Howroyd, Jan 22 2021

A218090 Number of unlabeled point-determining bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 8, 17, 63, 224, 1248, 8218, 75992, 906635, 14447433, 303100595, 8415834690, 309390830222, 15105805368214, 982300491033887

Offset: 0

Andy Hardt, Oct 20 2012

A graph is point-determining if no two vertices have the same set of neighbors. This kind of graph is also called a mating graph.

			Consider n = 3. The triangle graph is point-determining, but it is not bipartite, so it is not counted in a(3). The graph *--*--* is bipartite, but it is not point-determining (the vertices on the two ends have the same neighborhood), so it is also not counted in a(3). The only graph counted in a(3) is the graph *--*  *. - _Justin M. Troyka_, Nov 27 2013

Ira Gessel and Ji Li, Enumeration of point-determining graphs, arXiv:0705.0042 [math.CO]
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO].

Cf. A006024, A004110 (labeled and unlabeled point-determining graphs).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs).
Cf. A232699 (labeled point-determining bipartite graphs).
Cf. A232700, A088974 (labeled and unlabeled connected point-determining bipartite graphs).

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Original entry on oeis.org

1, 1, 1, 3, 21, 369, 16929, 1913682, 546626268, 406959998851, 808598348346150, 4358157210587930509, 64443771774627635711718, 2636248889492487709302815665, 300297332862557660078111708007894, 95764277032243987785712142452776403618, 85885545190811866954428990373255822969983915

Offset: 0

Goran Kilibarda, Vladeta Jovovic, Jan 14 2005

nonn

			a(3) = 3 because there are 2 distinct orientations of the triangle K_3 plus the empty graph on 3 vertices.

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

Cf. A100569 (labeled case), A100548, A101388, A004110, A004108, A059166, A059167, A001174.

\\ See links in A339645 for combinatorial species functions.
oedges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
ographsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 3^oedges(p) * sMonomial(p)); s/n!}
ographs(n)={sum(k=0, n, ographsCycleIndex(k)*x^k) + O(x*x^n)}
trees(n,k)={sRevert(x*sv(1)/sExp(k*x*sv(1) + O(x^n)))}
cycleIndexSeries(n)={my(g=ographs(n), tr=trees(n,2), tu=tr-tr^2); sSolve( g/sExp(tu), tr )*symGroupSeries(n)}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020

\\ faster stand-alone version
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]-1)\2)}
seq(n)={Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 3^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^2 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2))} \\ Andrew Howroyd, Jan 22 2021

a(0)=1 prepended and terms a(9) and beyond from Andrew Howroyd, Dec 27 2020

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

A241904 The number of graphs G on n vertices such that every unlabeled automorphism of the reduced graph of G is a labeled automorphism of the reduced graph of G.

Original entry on oeis.org

1, 2, 3, 8, 22, 110

Offset: 1

Dayana Adatorwovor, May 01 2014

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press (1999).

J. P. McSorley and T. D. Porter, K_p Removable Sequences of Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 45, 43-62, (2003).

Cf. A004110, A004108, A241905 (similar but with connected graphs).

A241905 The number of connected graphs G on n vertices such that every unlabeled automorphism of the reduced graph of G is a labeled automorphism of the reduced graph of G.

Original entry on oeis.org

1, 1, 1, 4, 13, 83

Offset: 1

Dayana Adatorwovor, May 01 2014

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press (1999).

J. P. McSorley and T. D. Porter, K_p Removable Sequences of Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 45, 43-62, (2003).

Cf. A004110, A004108, A241904 (similar but graphs not necessarily connected).

A369284 Number of point-determining graphs on n unlabeled nodes with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 1, 4, 12, 66, 522, 7525, 198389, 9816493, 903092383, 153733197077, 48444061519659, 28363852590188969, 30996574583203962119, 63502062798039684795935, 244852576446682783722245053, 1783161675023082411226026322655, 24603891461799405333437840036319801

Offset: 0

Andrew Howroyd, Jan 18 2024

nonn

Point-determining graphs are also called mating graphs. See A004110 for references.

The inverse Euler transform of this sequence gives A004108 except with a(1) = 0 and a(2) = 1.

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

Cf. A004108, A004110 (point-determining graphs).

a(n) = A004110(n) - a(n-1) for n > 0.

G.f.: B(x)/(1 + x) where B(x) is the g.f. of A004110.

cp's OEIS Frontend

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A101388 Number of n-vertex unlabeled digraphs without endpoints.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A218090 Number of unlabeled point-determining bipartite graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

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

A241904 The number of graphs G on n vertices such that every unlabeled automorphism of the reduced graph of G is a labeled automorphism of the reduced graph of G.

Views

Author

Keywords

References

Links

Crossrefs

A241905 The number of connected graphs G on n vertices such that every unlabeled automorphism of the reduced graph of G is a labeled automorphism of the reduced graph of G.

Views

Author

Keywords

References

Links

Crossrefs

A369284 Number of point-determining graphs on n unlabeled nodes with no isolated vertices.

Views

Author

Keywords