cp's OEIS Frontend

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

%I A141580 #17 Sep 16 2019 04:30:22
%S A141580 0,1,2,6,18,78,456,4299,68754,1990286,106088988,10454883132,
%T A141580 1904236651216,641859005526860,401547534010157680,
%U A141580 467956331904669136874,1019785644052109276678788,4171197546082606538129623140
%N A141580 Number of unlabeled non-mating graphs with n vertices.
%C A141580 a(n) is the difference between A000088 (number of graphs on n unlabeled nodes) and A004110 (number of n-node graphs without endpoints)
%C A141580 A non-mating graph has two vertices with an identical set of neighbors.
%C A141580 The adjacency matrix of a non-mating graph is degenerate.
%C A141580 Also the number of unlabeled graphs with n vertices and at least one endpoint. - _Gus Wiseman_, Sep 11 2019
%H A141580 Andrew Howroyd, <a href="/A141580/b141580.txt">Table of n, a(n) for n = 1..50</a>
%H A141580 Ronald C. Read, <a href="https://oeis.org/A006023/a006023.pdf">The enumeration of mating-type graphs</a>, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
%H A141580 Gus Wiseman, <a href="/A141580/a141580.png">The a(1) = 1 through a(5) = 18 non-mating graphs (isolated vertices not shown).</a>
%H A141580 Gus Wiseman, <a href="/A141580/a141580_1.png">The a(1) = 1 through a(5) = 18 graphs with at least one endpoint (isolated vertices not shown).</a>
%F A141580 a(n) = A000088(n) - A004110(n).
%e A141580 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.
%e A141580 From _Gus Wiseman_, Sep 11 2019: (Start)
%e A141580 Non-isomorphic representatives of the a(2) = 1 through a(5) non-mating graph edge-sets:
%e A141580   {12}  {12}     {12}           {12}
%e A141580         {13,23}  {12,34}        {12,34}
%e A141580                  {13,23}        {13,23}
%e A141580                  {13,24,34}     {12,35,45}
%e A141580                  {14,24,34}     {13,24,34}
%e A141580                  {14,23,24,34}  {14,24,34}
%e A141580                                 {12,34,35,45}
%e A141580                                 {13,24,35,45}
%e A141580                                 {14,23,24,34}
%e A141580                                 {14,25,35,45}
%e A141580                                 {15,25,35,45}
%e A141580                                 {12,25,34,35,45}
%e A141580                                 {14,25,34,35,45}
%e A141580                                 {15,23,24,35,45}
%e A141580                                 {15,25,34,35,45}
%e A141580                                 {13,24,25,34,35,45}
%e A141580                                 {15,24,25,34,35,45}
%e A141580                                 {15,23,24,25,34,35,45}
%e A141580 (End)
%t A141580 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
%Y A141580 The labeled version is A327379.
%Y A141580 Cf. A000088, A004110, A028242, A059167, A245797, A327335, A327371.
%K A141580 nonn
%O A141580 1,3
%A A141580 _Tanya Khovanova_, Aug 19 2008
%E A141580 Extended by _R. J. Mathar_, Sep 12 2008