[seqfan] Multiplicative Graphs

[franktaw at netscape.net]

For a given graph, suppose we take the product of the valences of the 
vertices.

The question is how many graphs have a given product.  To avoid 
infinities, we will consider only one-component graphs; that is, 
connected graphs excluding the empty graph.  (If we allow the the empty 
graph, a(1) will be one larger.)

Since valence 1 nodes don't directly affect the product, we can look at 
the graph that results when they 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.  Furthermore, each such 
labeling, up to graph equivalence, uniquely defines the original graph 
-- so this gives us a way to compute the sequence.

For a given n, we need only look at connected graphs with at most 
BigOmega(n) (A001222) nodes.  In particular, if n is prime, a(n) = 1, 
and if n is a semiprime, a(n) = 2.

Hand-calculating, and starting with n = 0 (the one-point graph), I get:

1,1,1,1,2,1,2,1,4,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,23,1,2,2,16,1,6,1,6,6,2,1

I don't know what a(48) is.

I would appreciate it if someone could (1) verify these values, and (2) 
compute some more.  Anything else anyone can contribute about the 
sequence would also be welcome.

Franklin T. Adams-Watters