login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006024 Number of labeled mating graphs with n nodes. Also called point-determining graphs.
(Formerly M3650)
25
1, 1, 1, 4, 32, 588, 21476, 1551368, 218608712, 60071657408, 32307552561088, 34179798520396032, 71474651351939175424, 296572048493274368856832, 2448649084251501449508762880, 40306353989748719650902623919616 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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, 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). - R. C. Read (rcread(AT)math.uwaterloo.ca) 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

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 A219149 A013041 * A118995 A222829 A134087

Adjacent sequences:  A006021 A006022 A006023 * A006025 A006026 A006027

KEYWORD

nonn

AUTHOR

Simon Plouffe

EXTENSIONS

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

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

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 February 19 07:51 EST 2019. Contains 320309 sequences. (Running on oeis4.)