login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A232699 Number of labeled point-determining bipartite graphs on n vertices. 4
1, 1, 1, 3, 15, 135, 1875, 38745, 1168545, 50017905, 3029330745, 257116925835, 30546104308335, 5065906139629335, 1172940061645387035, 379092680506164049425, 171204492289446788997825, 108139946568584292606269025, 95671942593719946611454522225 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

LINKS

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.

FORMULA

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)

EXAMPLE

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

MATHEMATICA

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

PROG

(PARI) 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

CROSSREFS

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

Sequence in context: A246804 A230166 A059861 * A030539 A028362 A195764

Adjacent sequences:  A232696 A232697 A232698 * A232700 A232701 A232702

KEYWORD

nonn

AUTHOR

Justin M. Troyka, Nov 27 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 7 12:05 EDT 2021. Contains 343650 sequences. (Running on oeis4.)