login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141580 Number of unlabeled non-mating 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 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

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

FORMULA

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

EXAMPLE

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)

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

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 April 11 16:42 EDT 2021. Contains 342888 sequences. (Running on oeis4.)