1,3

A mating graph is one in which no two vertices have identical adjacencies with the other vertices. - R. C. Read (rcread(AT)math.uwaterloo.ca) and Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 10 2003

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

D. Sumner, Point determination in graphs, Discrete Mathematics, volume 5, pp. 179-187, 1975.

I. Gessel and J. Li, On Point-Determining Graphs, arXiv:0705.0042, 2007.

a(n) = Sum_{k=0..n} stirling1(n, k)*2^binomial(k, 2). - R. C. Read (rcread(AT)math.uwaterloo.ca) and Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 10 2003

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

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.

(PARI) a(n)=n!*polcoeff(sum(k=0, n, 2^(k*(k-1)/2)*log(1+x+x*O(x^n))^k/k!), n) [From Paul D. Hanna (pauldhanna(AT)juno.com), May 20 2009]

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.

Sequence in context: A086899 A012509 A013041 this_sequence A118995 A134087 A132854

Adjacent sequences: A006021 A006022 A006023 this_sequence A006025 A006026 A006027

nonn

Simon Plouffe (simon.plouffe(AT)gmail.com)

More terms from R. C. Read (rcread(AT)math.uwaterloo.ca) and Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 10 2003