A079306 -id:A079306 - cp's OEIS frontend

A006024 Number of labeled mating graphs with n nodes. Also called point-determining graphs.

1, 1, 1, 4, 32, 588, 21476, 1551368, 218608712, 60071657408, 32307552561088, 34179798520396032, 71474651351939175424, 296572048493274368856832, 2448649084251501449508762880, 40306353989748719650902623919616

Offset: 0

Simon Plouffe

nonn

A mating graph is one in which no two vertices have identical adjacencies with the other vertices. - Ronald C. Read and Vladeta Jovovic, Feb 10 2003

Also number of (n-1)-node labeled mating graphs allowing loops and without isolated nodes. - Vladeta Jovovic, Mar 08 2008

			Consider the square (cycle of length 4) on vertices 1, 2, 3 and 4 in that order. Join a fifth vertex (5) to vertices 1, 3 and 4. The resulting graph is not a mating graph since vertices 1 and 3 both have the set {2, 4, 5} as neighbors. If we delete the edge (1,5) then the resulting graph is a mating graph: the neighborhood sets for vertices 1, 2, 3, 4 and 5 are respectively {2,4}, {1,3}, {2,4,5}, {1,3,5} and {3,4} - all different.

R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
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
I. M. Gessel and J. Li, Enumeration of Point-Determining Graphs, arXiv:0705.0042 [math.CO], 2007-2009.
I. M. Gessel and J. Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
R. C. Read, The Enumeration of Mating-Type Graphs, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989. (Annotated scanned copy)
D. Sumner, Point determination in graphs, Discrete Mathematics 5 (1973), 179-187.

Cf. A006025.
Cf. bi-point-determining graphs: labeled A129583, unlabeled A129584; connected bi-point-determining graphs: labeled A129585, unlabeled A129586; phylogenetic trees: labeled A000311, unlabeled A000669.
Cf. A007833, A079306 (connected)

a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];
Array[a, 15] (* Jean-François Alcover, Jul 25 2018 *)

a(n)=n!*polcoeff(sum(k=0,n,2^(k*(k-1)/2)*log(1+x+x*O(x^n))^k/k!),n) \\ Paul D. Hanna, May 20 2009

a(n) = Sum_{k=0..n} Stirling1(n, k)*2^binomial(k, 2). - Ronald C. Read and Vladeta Jovovic, Feb 10 2003

E.g.f.: Sum_{n>=0} 2^(n(n-1)/2)*log(1+x)^n/n!. - Paul D. Hanna, May 20 2009

More terms from Ronald C. Read and Vladeta Jovovic, Feb 10 2003

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

A079307 Number of n-node labeled mating digraphs whose complements are connected.

Original entry on oeis.org

1, 2, 47, 3537, 990504, 1052216730, 4368243719790, 71899754628285990, 4719127231162959826680, 1237680394434222243386835240, 1297992518900121521819851167607200

Offset: 1

Vladeta Jovovic, Feb 09 2003

nonn

Cf. A006024, A006025, A079306.

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

Original entry on oeis.org

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)

A129584 Number of unlabeled bi-point-determining graphs: graphs in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

Original entry on oeis.org

1, 0, 0, 1, 6, 36, 324, 5280, 156088, 8415760

Offset: 1

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

This is the unlabeled case of bi-point-determining graphs, which are basically graphs that are both point-determining (no two vertices have the same neighborhoods) and co-point-determining (graphs whose complements are point-determining)

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.

A129583 Number of labeled bi-point-determining graphs with n vertices.

Original entry on oeis.org

1, 1, 0, 0, 12, 312, 13824, 1147488, 178672128, 52666091712, 29715982846848, 32452221242518272, 69259424722321036032, 291060255757818125657088, 2421848956937579216663491584, 40050322614433939228627991906304, 1319551659023608317386779165849208832

Offset: 0

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

A bi-point determining graph is a graph in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

Andrew Howroyd, Table of n, a(n) for n = 0..50
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.

seq(n)={my(g=sum(k=0, n, 2^binomial(k,2)*x^k/k!) + O(x*x^n)); Vec(serlaplace(subst(g, x, 2*log(1+x+O(x*x^n))-x)))} \\ Andrew Howroyd, May 06 2021

E.g.f.: G(2*log(1+x)-x) where G(x) is the e.g.f. of A006125.

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, May 06 2021

A129585 Number of labeled connected bi-point-determining graphs with n vertices (see A129583).

Original entry on oeis.org

1, 1, 0, 0, 12, 252, 12312, 1061304, 170176656, 51134075424, 29204599254624, 32130964585236096, 68873851786953047040, 290164895151435531345024, 2417786648013402212500060416, 40014055814155246577685250570752, 1318911434129029730677931158374449664

Offset: 0

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

The calculation of connected bi-point-determining graphs is carried out by examining the connected components of bi-point-determining graphs. For more details, see reference.

Andrew Howroyd, Table of n, a(n) for n = 0..50
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.

max = 15; f[x_] := x + Log[ Sum[ 2^Binomial[n, 2]*((2*Log[1 + x] - x)^n/n!), {n, 0, max}]/(1 + x)]; A129585 = Drop[ CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]!, 1](* Jean-François Alcover, Jan 13 2012, after e.g.f. *)

seq(n)={my(g=sum(k=0, n, 2^binomial(k,2)*x^k/k!) + O(x*x^n)); Vec(serlaplace(1+x+log(subst(g, x, 2*log(1+x+O(x*x^n))-x)/(1+x))))} \\ Andrew Howroyd, May 06 2021

E.g.f.: 1 + x + log((Sum_{n>=0} 2^binomial(n,2)*(2*log(1+x)-x)^n/n!)/(1+x)). - Goran Kilibarda, Vladeta Jovovic, May 09 2007

E.g.f.: 1 + x + log(B(x)/(1+x)) where B(x) is the e.g.f. of A129583. - Andrew Howroyd, May 06 2021

More terms from Goran Kilibarda, Vladeta Jovovic, May 09 2007

a(0)=1 prepended and terms a(16) and beyond from Andrew Howroyd, May 06 2021

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

Original entry on oeis.org

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

cp's OEIS Frontend

A006024 Number of labeled mating graphs with n nodes. Also called point-determining graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A079307 Number of n-node labeled mating digraphs whose complements are connected.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

A129584 Number of unlabeled bi-point-determining graphs: graphs in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

Views

Author

Keywords

Comments

Links

Crossrefs

A129583 Number of labeled bi-point-determining graphs with n vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A129585 Number of labeled connected bi-point-determining graphs with n vertices (see A129583).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions