A004108 -id:A004108 - cp's OEIS frontend

A129586 Number of unlabeled connected bi-point-determining graphs (see A129583).

1, 0, 0, 1, 5, 31, 293, 4986, 151096, 8264613, 812528493, 144251345591, 46649058611515, 27744159658789435, 30603223477819571330, 63039669933956074333128, 243839768084859914114367906, 1779006737976575676931317142360, 24571827603944282248499044846893618

Offset: 1

Ji Li (vieplivee(AT)hotmail.com), May 07 2007

The calculation of the number of connected bi-point-determining graphs is carried out by examining the connected components of bi-point-determining graphs. For more details, see linked paper "Enumeration of point-determining Graphs".

Martin Rubey, Table of n, a(n) for n = 1..29
Florian Fürnsinn, Moritz Gangl, and Martin Rubey, Unexpectedly, a symmetry on unlabeled graphs, arXiv:2505.03665 [math.CO], 2025. See p. 18.
Ira M. Gessel and Ji Li, Enumeration of point-determining Graphs, Journal of Combinatorial Theory, Series A 118 (2011) 591-612.

Cf. graphs: labeled A006125, unlabeled A000568; connected graphs: labeled A001187, unlabeled A001349; point-determining graphs: labeled A006024, unlabeled A004110; connected point-determining graphs: labeled A092430, unlabeled A004108; connected co-point-determining graphs: labeled A079306, unlabeled A004108; bi-point-determining graphs: labeled A129583, unlabeled A129584; connected bi-point-determining graphs: labeled A129585, unlabeled A129586; phylogenetic trees: labeled A000311, unlabeled A000669.

151096 and 8264613 from Vladeta Jovovic, May 10 2007

a(n) for n >= 11 from Martin Rubey, May 08 2025

A232699 Number of labeled point-determining bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 1, 3, 15, 135, 1875, 38745, 1168545, 50017905, 3029330745, 257116925835, 30546104308335, 5065906139629335, 1172940061645387035, 379092680506164049425, 171204492289446788997825, 108139946568584292606269025, 95671942593719946611454522225

Offset: 0

Justin M. Troyka, Nov 27 2013

nonn

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.
a(n) is always odd.
For every prime p > 2, a(n) is divisible by p for all n >= p.  It follows that, if m is odd and squarefree with largest prime factor q, then a(n) is divisible by m for all n >= q.  A similar property appears to hold for odd prime powers, in which case it would hold for all odd numbers.

			Consider n = 3. The triangle graph is point-determining, but it is not bipartite, so it is not counted in a(3). The graph 1--2--3 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 *--*  * (with three possible labelings). - _Justin M. Troyka_, Nov 27 2013

Andrew Howroyd, Table of n, a(n) for n = 0..100 (terms 0..20 from Justin M. Troyka)
Ira Gessel and Ji Li, Enumeration of point-determining graphs, arXiv:0705.0042 [math.CO], 2007-2009.
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO], 2013.

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

terms = 20;
CoefficientList[Sqrt[Sum[((1+x)^2^k Log[1+x]^k)/k!, {k, 0, terms}]] + O[x]^terms, x] Range[0, terms-1]! (* Jean-François Alcover, Sep 13 2018, after Andrew Howroyd *)

seq(n)={my(A=log(1+x+O(x*x^n))); Vec(serlaplace(sqrt(sum(k=0, n, exp(2^k*A)*A^k/k!))))} \\ Andrew Howroyd, Sep 09 2018

From Andrew Howroyd, Sep 09 2018: (Start)
a(n) = Sum_{k=0..n} Stirling1(n,k)*A047864(k).
E.g.f: sqrt(Sum_{k=0..n} exp(2^k*log(1+x))*log(1+x)^k/k!). (End)

A232700 Number of labeled connected point-determining bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 0, 12, 60, 1320, 26880, 898800, 40446000, 2568736800, 225962684640, 27627178692960, 4686229692144000, 1104514965434200320, 361988888631722352000, 165271302775469812521600, 105278651889065640047462400, 93750696652129931568573619200

Offset: 1

Justin M. Troyka, Nov 27 2013

nonn

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.

For all n >= 3, a(n) is even. For every prime p > 2, a(n) is divisible by p for all n >= p. It follows that, if m is squarefree with largest prime factor q, then a(n) is divisible by m for all n >= q. A similar property appears to hold for prime powers, in which case it would hold for all numbers.

			Consider n = 4.  There are 12 connected point-determining bipartite graphs on 4 vertices: the graph *--*--*--*, with 12 possible labelings. - _Justin M. Troyka_, Nov 27 2013

Andrew Howroyd, Table of n, a(n) for n = 1..100 (terms 1..20 from Justin M. Troyka)
Ira Gessel and Ji Li, Enumeration of point-determining graphs, arXiv:0705.0042 [math.CO], 2007-2009.
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO], 2013.

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

terms = 18;
G[x_] = Sqrt[Sum[((1 + x)^2^k*Log[1 + x]^k)/k!, {k, 0, terms+1}]] + O[x]^(terms+1);
A[x_] = x + Log[1 + (G[x] - x - 1)/(1 + x)];
(CoefficientList[A[x], x]*Range[0, terms]!) // Rest (* Jean-François Alcover, Sep 13 2018, after Andrew Howroyd *)

seq(n)={my(A=log(1+x+O(x*x^n))); my(p=sqrt(sum(k=0, n, exp(2^k*A)*A^k/k!))); Vec(serlaplace(x + log(1+(p-x-1)/(1+x))))} \\ Andrew Howroyd, Sep 09 2018

E.g.f.: x + log(1 + (G(x)-x-1)/(1+x)) where G(x) is the e.g.f. of A232699. - Andrew Howroyd, Sep 09 2018

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

A304222 Triangle T(n,k) read by rows: number of simple connected graphs with n nodes and k endpoints, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 0, 11, 5, 3, 1, 1, 0, 61, 29, 14, 5, 2, 1, 0, 507, 224, 86, 25, 8, 2, 1, 0, 7442, 2666, 762, 184, 48, 11, 3, 1, 0, 197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0, 9808209, 1653431, 220627, 29252, 4252, 660, 115, 20, 4, 1, 0

Offset: 0

R. J. Mathar, May 11 2018

Endpoints are vertices with 0 or 1 (less than 2) edges.

			The triangle starts in row n=0 with column 0 <= k <= n as:
       1;
       1,     0;
       0,     0,     1;
       1,     0,     1,    0;
       3,     1,     1,    1,   0;
      11,     5,     3,    1,   1,  0;
      61,    29,    14,    5,   2,  1,  0;
     507,   224,    86,   25,   8,  2,  1, 0;
    7442,  2666,   762,  184,  48, 11,  3, 1, 0;
  197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0;

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

Cf. A001349 (row sums), A004108 (first column), A055290 (trees only), A327371.

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i) )}
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)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)}
T(n)={my(v=InvEulerMT(Vec(G(n)-1))); v[2]=y^2; concat([[1]], vector(#v, n, Vecrev(v[n], n+1))) }
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 22 2021

Terms a(55) and beyond from Andrew Howroyd, Jan 22 2021

A349402 Number of distance-critical graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 4, 15, 168, 2252, 94504

Offset: 1

Gabrielle Tauscheck, Nov 15 2021

A distance-critical graph is considered to be a connected graph such that no vertex can be deleted without altering the distance metric on the remaining vertices.

			The unique distance-critical graphs on 5 and 6 vertices are the cycles.

Joshua Cooper and Gabrielle Tauscheck, Distance Critical Graphs, arXiv:2405.09656 [math.CO], 2024. See p. 3.

Cf. A004108.

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

cp's OEIS Frontend

A129586 Number of unlabeled connected bi-point-determining graphs (see A129583).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A232699 Number of labeled point-determining bipartite graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A232700 Number of labeled connected point-determining bipartite graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A304222 Triangle T(n,k) read by rows: number of simple connected graphs with n nodes and k endpoints, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI