A006023 -id:A006023 - cp's OEIS frontend

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

1, 1, 1, 2, 5, 16, 78, 588, 8047, 205914, 10014882, 912908876, 154636289460, 48597794716736, 28412296651708628, 31024938435794151088, 63533059372622888758054, 244916078509480823407040988, 1783406527599529094009748567708, 24605674623474428415849066062642456

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the number of unlabeled mating graphs with n nodes. A mating graph has no two vertices with identical sets of neighbors. - Tanya Khovanova, Oct 23 2008

F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.
F. Harary and E. Palmer, Graphical Enumeration, (1973), compare formula (8.7.11).
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Ira M. Gessel and Ji Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
R. J. Mathar, Illustrations for n=1..5 nodes.
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
R. W. Robinson, Graphs without endpoints - computer printout.
N. J. A. Sloane, Illustration of a(0)-a(5).

Row sums of A123551.
Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A006024 (number of labeled mating graphs with n nodes), A129584 (bi-point-determining graphs).
If isolated nodes are forbidden, see A261919.
Cf. A000088.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t * k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Sum[permcount[p] * 2^edges[p] * Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; a[0] = 1;
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 27 2018, after Andrew Howroyd *)

\\ Compare A000088.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s} \\ Andrew Howroyd, Sep 09 2018

A006024 Number of labeled mating graphs with n nodes. Also called point-determining graphs.

Original entry on oeis.org

1, 1, 1, 4, 32, 588, 21476, 1551368, 218608712, 60071657408, 32307552561088, 34179798520396032, 71474651351939175424, 296572048493274368856832, 2448649084251501449508762880, 40306353989748719650902623919616

Offset: 0

Simon Plouffe

nonn

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

			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.

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

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.

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, A079306 (connected)

a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];
Array[a, 15] (* Jean-François Alcover, Jul 25 2018 *)

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

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

More terms from Ronald C. Read and Vladeta Jovovic, Feb 10 2003

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

A141580 Number of unlabeled non-mating graphs with n vertices.

Original entry on oeis.org

0, 1, 2, 6, 18, 78, 456, 4299, 68754, 1990286, 106088988, 10454883132, 1904236651216, 641859005526860, 401547534010157680, 467956331904669136874, 1019785644052109276678788, 4171197546082606538129623140

Offset: 1

Tanya Khovanova, Aug 19 2008

nonn

a(n) is the difference between A000088 (number of graphs on n unlabeled nodes) and A004110 (number of n-node graphs without endpoints)
A non-mating graph has two vertices with an identical set of neighbors.
The adjacency matrix of a non-mating graph is degenerate.
Also the number of unlabeled graphs with n vertices and at least one endpoint. - Gus Wiseman, Sep 11 2019

			A cycle with 4 vertices is a non-mating graph. In the standard ordering of vertices, vertices 1 and 3 are both connected to vertices 2 an 4, thus having an identical sets of neighbors.
From _Gus Wiseman_, Sep 11 2019: (Start)
Non-isomorphic representatives of the a(2) = 1 through a(5) non-mating graph edge-sets:
  {12}  {12}     {12}           {12}
        {13,23}  {12,34}        {12,34}
                 {13,23}        {13,23}
                 {13,24,34}     {12,35,45}
                 {14,24,34}     {13,24,34}
                 {14,23,24,34}  {14,24,34}
                                {12,34,35,45}
                                {13,24,35,45}
                                {14,23,24,34}
                                {14,25,35,45}
                                {15,25,35,45}
                                {12,25,34,35,45}
                                {14,25,34,35,45}
                                {15,23,24,35,45}
                                {15,25,34,35,45}
                                {13,24,25,34,35,45}
                                {15,24,25,34,35,45}
                                {15,23,24,25,34,35,45}
(End)

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(1) = 1 through a(5) = 18 non-mating graphs (isolated vertices not shown).
Gus Wiseman, The a(1) = 1 through a(5) = 18 graphs with at least one endpoint (isolated vertices not shown).

The labeled version is A327379.

Cf. A000088, A004110, A028242, A059167, A245797, A327335, A327371.

k = {}; For[i = 1, i < 8, i++, lg = ListGraphs[i] ; len = Length[lg]; k = Append[k, Length[Select[Range[len], Length[Union[ToAdjacencyMatrix[lg[[ # ]]]]] != i &]]]]; k

a(n) = A000088(n) - A004110(n).

Extended by R. J. Mathar, Sep 12 2008

A006025 Number of labeled mating digraphs with n nodes.

Original entry on oeis.org

1, 1, 3, 54, 3750, 1009680, 1058347920, 4375678520640, 71934792452208000, 4719774805970453006400, 1237727595442264073683462080, 1298006134163762816201615178698880, 5444432200219729912412940250057668378240

Offset: 0

Simon Plouffe

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
R. C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

Cf. A006024.

a[0] = 1; a[n_] := Sum[StirlingS1[n , k]*2^(k^2 - k), {k, 0, n}];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Aug 16 2019 *)

a(n)=n!*polcoeff(sum(k=0,n,2^(k*(k-1))*log(1+x+x*O(x^n))^k/k!),n) \\ Paul D. Hanna, May 20 2009

a(n) = Sum_{k=0..n} Stirling1(n, k)*2^(k^2-k). - Vladeta Jovovic, Feb 11 2003

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

More terms from Vladeta Jovovic, Feb 11 2003

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

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 05 2019

nonn

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

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.

The unlabeled version is A141580.

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

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

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

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

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

cp's OEIS Frontend

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A006024 Number of labeled mating graphs with n nodes. Also called point-determining graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A141580 Number of unlabeled non-mating graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A006025 Number of labeled mating digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions