

A141580


Number of unlabeled nonmating graphs with n vertices.


7



0, 1, 2, 6, 18, 78, 456, 4299, 68754, 1990286, 106088988, 10454883132, 1904236651216, 641859005526860, 401547534010157680, 467956331904669136874, 1019785644052109276678788, 4171197546082606538129623140
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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


LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of matingtype graphs, Report CORR 8938, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(1) = 1 through a(5) = 18 nonmating 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).


FORMULA

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


EXAMPLE

A cycle with 4 vertices is a nonmating 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)
Nonisomorphic representatives of the a(2) = 1 through a(5) nonmating graph edgesets:
{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)


MATHEMATICA

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


CROSSREFS

The labeled version is A327379.
Cf. A000088, A004110, A028242, A059167, A245797, A327335, A327371.
Sequence in context: A162058 A113844 A266858 * A007869 A263915 A144557
Adjacent sequences: A141577 A141578 A141579 * A141581 A141582 A141583


KEYWORD

nonn


AUTHOR

Tanya Khovanova, Aug 19 2008


EXTENSIONS

Extended by R. J. Mathar, Sep 12 2008


STATUS

approved



