

A166974


Number of singlecomponent graphs where the product of the valences of the nodes is n.


1



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

A singlecomponent graph is any nonempty connected graph. If the empty graph was allowed, a(1) would be 2 instead of 1.
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.
Note, in particular, that a(n) = 1 for any prime, and 2 for any semiprime.
This product for the complete graph on n points is (n1)^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.


LINKS

Andrew Weimholt, Table of n, a(n) for n = 0..255


CROSSREFS

Cf. A000079, A001222 (BigOmega), A001349, A002905, A007778, A062275.
Sequence in context: A319002 A050363 A308063 * A292504 A281118 A284289
Adjacent sequences: A166971 A166972 A166973 * A166975 A166976 A166977


KEYWORD

nice,nonn


AUTHOR

Franklin T. AdamsWatters, Oct 26 2009


EXTENSIONS

Corrected and extended by Andrew Weimholt, Oct 26 2009


STATUS

approved



