cp's OEIS Frontend

A166974 Number of single-component graphs where the product of the valences of the nodes is n.

%I A166974 #9 Nov 09 2018 15:36:23
%S A166974 1,1,1,1,2,1,2,1,4,2,2,1,6,1,2,2,8,1,6,1,6,2,2,1,16,2,2,4,6,1,8,1,16,
%T A166974 2,2,2,25,1,2,2,16,1,8,1,6,6,2,1,46,2,6,2,6,1,18,2,16,2,2,1,36,1,2,6,
%U A166974 40,2,8,1,6,2,8,1,84,1,2,6,6,2,8,1,49,12,2,1,36,2,2,2,16,1,38,2,6,2,2,2,137
%N A166974 Number of single-component graphs where the product of the valences of the nodes is n.
%C A166974 A single-component graph is any nonempty connected graph. If the empty graph was allowed, a(1) would be 2 instead of 1.
%C A166974 The sequence can be computed for n > 1 by looking at the graph that results when all valence 1 nodes are removed. This will be a connected graph, and labeling each node with its original valence, the product of the labels will be the original product. Each node must be labeled with at least its valence, and at least 2. Each such labeling, up to graph equivalence, uniquely defines the original graph, so we need only count the labelings for connected graphs with up to BigOmega(n) nodes.
%C A166974 Note, in particular, that a(n) = 1 for any prime, and 2 for any semiprime.
%C A166974 This product for the complete graph on n points is (n-1)^n. For the complete bipartite graph with n and m points in the parts the product is n^m*m^n. For the cyclic graph with n nodes it is 2^n.
%H A166974 Andrew Weimholt, <a href="/A166974/b166974.txt">Table of n, a(n) for n = 0..255</a>
%Y A166974 Cf. A000079, A001222 (BigOmega), A001349, A002905, A007778, A062275.
%K A166974 nice,nonn
%O A166974 0,5
%A A166974 _Franklin T. Adams-Watters_, Oct 26 2009
%E A166974 Corrected and extended by _Andrew Weimholt_, Oct 26 2009