A007833 -id:A007833 - 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

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)

A007834 Number of point labeled reduced 5-free two-graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 1, 16, 76, 1016, 10284, 157340, 2411756, 44953712, 899824256, 20283419872, 495216726096, 13202082981712, 378896535199888, 11690436112988224, 385173160930360192, 13509981115738946816, 502374681770910293568, 19746124320077115154112, 817908018939079281840320

Offset: 1

Peter J. Cameron

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
P. J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4.

Row sums are A361355.

Cf. A007831, A007832, A007833, A359986.

CoefficientList[Series[-2*LambertW[-1/2*E^(-1/2)*(1+x)^(1/2)]/(1+x), {x, 0, 15}], x]* Range[0, 15]! (* Vaclav Kotesovec, Sep 30 2013 *)

\\ B(x) gives the e.g.f. of A359986.
B(n)={exp(2*x + intformal(serreverse(log(1 + x + O(x^n)) + log(1 + x + O(x^n)) - x)))}
seq(n)={Vec(serlaplace(log(subst(B(n), x, log(1 + x + O(x*x^n)))/(1 + x))))} \\ Andrew Howroyd, Oct 15 2024

E.g.f.: -2*LambertW(-1/2*exp(-1/2)*(1+x)^(1/2))/(1+x). - Vladeta Jovovic, Aug 21 2006
a(n) ~ sqrt(2)*sqrt(4-exp(1)) * n^(n-1) / (8*exp(n-1)*(4*exp(-1)-1)^n). - Vaclav Kotesovec, Sep 30 2013
E.g.f.: log(B(log(1 + x))/(1 + x)), where B(x) is the e.g.f. of A359986. - Andrew Howroyd, Oct 15 2024

a(20) onwards from Andrew Howroyd, Oct 15 2024

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

A007834 Number of point labeled reduced 5-free two-graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions