login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A166974 Number of single-component 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 single-component 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 (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.

LINKS

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

CROSSREFS

Cf. A000079, A001222 (BigOmega), A001349, A002905, A007778, A062275.

Sequence in context: A066389 A077191 A050363 * A281118 A284289 A111588

Adjacent sequences:  A166971 A166972 A166973 * A166975 A166976 A166977

KEYWORD

nice,nonn

AUTHOR

Franklin T. Adams-Watters, Oct 26 2009

EXTENSIONS

Corrected and extended by Andrew Weimholt, Oct 26 2009

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 29 01:38 EDT 2017. Contains 288855 sequences.