# [seqfan] Re: Multiplicative Graphs

Andrew Weimholt andrew at weimholt.com
Fri Oct 23 03:05:02 CEST 2009

```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.
>
>  Franklin T. Adams-Watters
>
>
>  _______________________________________________
>
>  Seqfan Mailing list - http://list.seqfan.eu/
>
>

```