# [seqfan] Multiplicative Graphs

franktaw at netscape.net franktaw at netscape.net
Thu Oct 22 11:06:48 CEST 2009

```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.