login
Number of unlabeled non-mating graphs with n vertices.
7

%I #17 Sep 16 2019 04:30:22

%S 0,1,2,6,18,78,456,4299,68754,1990286,106088988,10454883132,

%T 1904236651216,641859005526860,401547534010157680,

%U 467956331904669136874,1019785644052109276678788,4171197546082606538129623140

%N Number of unlabeled non-mating graphs with n vertices.

%C a(n) is the difference between A000088 (number of graphs on n unlabeled nodes) and A004110 (number of n-node graphs without endpoints)

%C A non-mating graph has two vertices with an identical set of neighbors.

%C The adjacency matrix of a non-mating graph is degenerate.

%C Also the number of unlabeled graphs with n vertices and at least one endpoint. - _Gus Wiseman_, Sep 11 2019

%H Andrew Howroyd, <a href="/A141580/b141580.txt">Table of n, a(n) for n = 1..50</a>

%H 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 Gus Wiseman, <a href="/A141580/a141580.png">The a(1) = 1 through a(5) = 18 non-mating graphs (isolated vertices not shown).</a>

%H 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 a(n) = A000088(n) - A004110(n).

%e 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 From _Gus Wiseman_, Sep 11 2019: (Start)

%e Non-isomorphic representatives of the a(2) = 1 through a(5) non-mating graph edge-sets:

%e {12} {12} {12} {12}

%e {13,23} {12,34} {12,34}

%e {13,23} {13,23}

%e {13,24,34} {12,35,45}

%e {14,24,34} {13,24,34}

%e {14,23,24,34} {14,24,34}

%e {12,34,35,45}

%e {13,24,35,45}

%e {14,23,24,34}

%e {14,25,35,45}

%e {15,25,35,45}

%e {12,25,34,35,45}

%e {14,25,34,35,45}

%e {15,23,24,35,45}

%e {15,25,34,35,45}

%e {13,24,25,34,35,45}

%e {15,24,25,34,35,45}

%e {15,23,24,25,34,35,45}

%e (End)

%t 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 The labeled version is A327379.

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

%K nonn

%O 1,3

%A _Tanya Khovanova_, Aug 19 2008

%E Extended by _R. J. Mathar_, Sep 12 2008