# [seqfan] Re: Multiplicative Graphs

franktaw at netscape.net franktaw at netscape.net
Fri Oct 23 07:04:51 CEST 2009

```I agree with both corrections.

However, I get a(48) = 45.

Continuing, I get:

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,24,1,2,2,16,1,6,1,6,6,2,1,
45,2,6,2,6,1,19,2,16,2,2,1,36,1,2,6

with a(64) being the next term to be computed.

I'd still like for somebody with some graph generation software to
compute these mechanically, preferably on to larger values.

-----Original Message-----
From: Andrew Weimholt <andrew at weimholt.com>

Hi Franklin,

nice idea for a sequence!
Your sequence is missing either a(9) or a(10)
>  1,1,1,1,2,1,2,1,4,2,1,6
should be
1,1,1,1,2,1,2,1,4,2,2,1,6,...

Also, by hand, I get a(36) = 24, not 23.

and I get a(48) = 42

Andrew

On 10/22/09, franktaw at netscape.net <franktaw at netscape.net> wrote:
> 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.
>
>
>
>  _______________________________________________
>
>  Seqfan Mailing list - http://list.seqfan.eu/
>
>

```