OFFSET
0,4
COMMENTS
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
REFERENCES
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).
LINKS
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.
FORMULA
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
EXAMPLE
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.
MATHEMATICA
a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];
Array[a, 15] (* Jean-François Alcover, Jul 25 2018 *)
PROG
(PARI) 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
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Ronald C. Read and Vladeta Jovovic, Feb 10 2003
a(0)=1 prepended by Andrew Howroyd, Sep 09 2018
STATUS
approved