A327379 Number of labeled non-mating-type graphs with n vertices.

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset: 1

Author

Gus Wiseman, Sep 05 2019

Keywords

• nonn

Comments

A mating-type graph has all different rows in its adjacency matrix.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
• Gus Wiseman, The a(4) = 32 non-mating-type graphs.

Crossrefs

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!UnsameQ@@AdjacencyMatrix[Graph[Range[n],#]]&]],{n,5}]

PARI

a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ Andrew Howroyd, Sep 11 2019

Formula

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019